25 条题解

  • 2
    @ 2014-03-02 15:38:47

    Link-cut Tree,up用维修数列的放法
    O(nlogn)

  • 1
    @ 2017-04-06 15:50:23

    Accepted

    状态 耗时 内存占用

    #1 Accepted 4ms 256.0KiB
    #2 Accepted 3ms 216.0KiB
    #3 Accepted 3ms 256.0KiB
    #4 Accepted 152ms 4.375MiB
    #5 Accepted 139ms 4.219MiB
    #6 Accepted 164ms 4.48MiB
    #7 Accepted 165ms 4.363MiB
    #8 Accepted 298ms 4.75MiB
    #9 Accepted 286ms 4.625MiB
    #10 Accepted 314ms 4.875MiB
    看见大家都是写的树剖。。。我为什么一来就想到了LCT……
    在Splay里面维护最大值,左边最大,右边最大,总和等一系列信息。
    每次询问先MakeRoot然后再Access,将根节点储存的最大值输出就行了。
    (总时间1531ms,估计是这次的评测机比较好。。。)
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    inline int read(){
    char c;int rec=0,f=1;
    while((c=getchar())<'0'||c>'9')if(c=='-')f=-1;
    while(c>='0'&&c<='9')rec=rec*10+c-'0',c=getchar();
    return rec*f;
    }
    int n,m;
    struct LCT_Tree{
    int F,s[2],val,size;
    int sum,maxx,pmax[2];
    int C,R;
    inline void NewNode(int fa,int x){
    F=fa;C=R=0;size=1;
    val=sum=maxx=pmax[0]=pmax[1]=x;
    return ;
    }
    }tree[100005];
    inline bool Isroot(int v){return tree[tree[v].F].s[0]!=v&&tree[tree[v].F].s[1]!=v;}
    inline void PMAX(int v,int f){
    tree[v].pmax[f]=max(tree[tree[v].s[f]].pmax[f],
    tree[tree[v].s[f]].sum+tree[v].val+max(0,tree[tree[v].s[!f]].pmax[f]));
    }
    inline void Up(int v){
    tree[v].size=tree[tree[v].s[0]].size+1+tree[tree[v].s[1]].size;
    tree[v].sum=tree[tree[v].s[0]].sum+tree[v].val+tree[tree[v].s[1]].sum;
    tree[v].maxx=max(max(tree[tree[v].s[0]].maxx,tree[tree[v].s[1]].maxx),
    max(0,tree[tree[v].s[0]].pmax[1])+tree[v].val+max(0,tree[tree[v].s[1]].pmax[0]));
    PMAX(v,0);PMAX(v,1);return ;
    }
    inline void Same(int v,int x){if(v==0)return ;
    tree[v].C=1;tree[v].val=x;tree[v].sum=x*tree[v].size;
    tree[v].maxx=tree[v].pmax[0]=tree[v].pmax[1]=max(x,tree[v].sum);
    return ;
    }
    inline void Rev(int v){if(v==0)return ;
    tree[v].R^=1;swap(tree[v].s[0],tree[v].s[1]);swap(tree[v].pmax[0],tree[v].pmax[1]);return ;
    }
    inline void Down(int v){
    if(tree[v].C){Same(tree[v].s[0],tree[v].val);Same(tree[v].s[1],tree[v].val);tree[v].C=0;}
    if(tree[v].R){Rev(tree[v].s[0]);Rev(tree[v].s[1]);tree[v].R=0;}
    return ;
    }
    inline void Lazy(int v){if(!Isroot(v))Lazy(tree[v].F);Down(v);return ;}
    inline void Rot(int v){
    int p=tree[v].F,g=tree[p].F;
    int t1=v==tree[p].s[1],t2=p==tree[g].s[1];
    int ch=tree[v].s[1^t1];
    if(!Isroot(p))tree[g].s[t2]=v;tree[ch].F=p;
    tree[v].F=g;tree[v].s[1^t1]=p;
    tree[p].F=v;tree[p].s[t1]=ch;
    Up(p);return;
    }
    inline void Splay(int v){Lazy(v);
    while(!Isroot(v)){
    int p=tree[v].F,g=tree[p].F;
    if(!Isroot(p))(v==tree[p].s[1])^(p==tree[g].s[0])?Rot(v):Rot(p);
    Rot(v);
    }Up(v);return;
    }
    inline void Access(int v){
    for(int temp=0;v;temp=v,v=tree[v].F)
    {Splay(v);tree[v].s[1]=temp;Up(v);}
    return ;
    }
    inline void Make_Root(int v){Access(v);Splay(v);Rev(v);return ;}
    inline void Link(int v1,int v2){Make_Root(v1);tree[v1].F=v2;return ;}
    inline int Find_Root(int v){while(!Isroot(v))v=tree[v].F;return v;}
    inline void Change(int v1,int v2,int x){Make_Root(v1);Access(v2);Same(Find_Root(v2),x);return ;}
    inline void Ask(int v1,int v2){Make_Root(v1);Access(v2);Splay(v2);cout<<tree[v2].maxx<<' ';return ;}
    int main(){
    n=read();
    for(int i=1;i<=n;i++)tree[i].NewNode(0,read());
    for(int i=1;i<n;i++)Link(read(),read());
    m=read();
    int x,y,z;
    for(int i=1;i<=m;i++){
    int f=read();
    if(f==1)Ask(read(),read());
    else {
    x=read();y=read();z=read();
    Change(x,y,z);
    }
    }cout<<'\n';
    return 0;
    }

  • 0
    @ 2016-10-16 15:58:29

    vector竟然如此不受待见QAQ(也有可能是我写废了,卡了好久)。
    用vector数组死活只能过3个点,其余TLE;用嵌套vector+resize能过,5000+ms;改成数组以后就2000+ms了。其他题目用vector存图都没有出现过这样的问题...如果有哪位大神知道原因请告知。

    思路大概就是树剖+线段树,线段树每个节点维护4个值,分别是区间内最大连续子序列求和、必须从左/右端点开始的最大连续子序列求和、区间求和,利用这些值查询结果什么的,以及Lazy。

    2000+ms版本:

    #include<iostream>
    #include<cstring>
    #include<vector>
    #include<cstdio>
    #define MAXN 100010
    #define INF 10000000
    using namespace std;
    
    int edge[MAXN<<1],pre[MAXN<<1],now[MAXN],tail;
    
    void ADD_EDGE(int u,int v)
    {
        edge[++tail]=v;pre[tail]=now[u];now[u]=tail;
        edge[++tail]=u;pre[tail]=now[v];now[v]=tail;
    }
    
    int dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],nw0[MAXN];
    
    void DFS(int u)
    {
        siz[u]=1;
        for(int i=now[u];i;i=pre[i])
        {
            int v=edge[i];
            if(v!=fa[u])
            {
                fa[v]=u;
                dep[v]=dep[u]+1;
                DFS(v);
                siz[u]+=siz[v];
                if(siz[v]>siz[son[u]]) son[u]=v;
            }
        }
    }
    
    int tid[MAXN],tidc=0,top[MAXN],nw1[MAXN];
    
    void CONNECT(int u,int tp)
    {
        tid[u]=++tidc;
        nw1[tid[u]]=nw0[u];
        top[u]=tp;
        if(son[u]) CONNECT(son[u],tp);
        for(int i=now[u];i;i=pre[i])
        {
            int v=edge[i];
            if(v!=fa[u]&&v!=son[u])
            {
                CONNECT(v,v);
            }
        }
    }
    
    #define lson(x) ((x<<1))
    #define rson(x) ((x<<1)|1)
    
    struct node
    {
        int l,u;
        int vt; 
    } N[MAXN<<2];
    
    struct state
    {
        int s[4]; //无限制、从左开始、从右开始、全部 
    } S[MAXN<<2];
    
    state inline UNION (const state &l,const state &r)
    {
        state ans;
        ans.s[0]=l.s[0]>r.s[0]?l.s[0]:r.s[0];
        ans.s[0]=ans.s[0]>(l.s[2]+r.s[1])?ans.s[0]:(l.s[2]+r.s[1]);
        ans.s[1]=l.s[1]>(l.s[3]+r.s[1])?l.s[1]:(l.s[3]+r.s[1]);
        ans.s[2]=r.s[2]>(r.s[3]+l.s[2])?r.s[2]:(r.s[3]+l.s[2]);
        ans.s[3]=l.s[3]+r.s[3];
        return ans;
    }
    
    void inline PUSHUP(int i)
    {
        S[i]=UNION(S[lson(i)],S[rson(i)]);
    }
    
    void inline PUSHDOWN(int i)
    {
        if(N[i].vt==INF) return;
        int ls=lson(i),rs=rson(i);
        S[ls].s[3]=(N[ls].u-N[ls].l+1)*N[i].vt;
        S[ls].s[0]=S[ls].s[1]=S[ls].s[2]=max(0,S[ls].s[3]);
        S[rs].s[3]=(N[rs].u-N[rs].l+1)*N[i].vt;
        S[rs].s[0]=S[rs].s[1]=S[rs].s[2]=max(0,S[rs].s[3]);
        N[ls].vt=N[rs].vt=N[i].vt;
        N[i].vt=INF;
    }
    
    void BUILD(int l,int u,int i)
    {
        N[i].l=l; N[i].u=u; N[i].vt=INF;
        if(l==u)
        {
            S[i].s[3]=nw1[l];
            S[i].s[0]=S[i].s[1]=S[i].s[2]=max(0,nw1[l]);
            return;
        }
        int m=(l+u)>>1;
        BUILD(l,m,lson(i));
        BUILD(m+1,u,rson(i));
        PUSHUP(i);
    }
    
    void UPDATE(int l,int u,int val,int i)
    {
        if(N[i].l==l&&N[i].u==u)
        {
            N[i].vt=val;
            S[i].s[3]=(u-l+1)*val;
            S[i].s[0]=S[i].s[1]=S[i].s[2]=max(0,S[i].s[3]);
            return;
        }
        PUSHDOWN(i);
        int m=(N[i].l+N[i].u)>>1;
        if(u<=m) UPDATE(l,u,val,lson(i));
        else if(l>m) UPDATE(l,u,val,rson(i));
        else
        {
            UPDATE(l,m,val,lson(i));
            UPDATE(m+1,u,val,rson(i));
        }
        PUSHUP(i);
    }
    
    state QUERY(int l,int u,int i)
    {
        if(N[i].l==l&&N[i].u==u)
        {
            return S[i];
        }
        PUSHDOWN(i);
        int m=(N[i].l+N[i].u)>>1;
        if(u<=m) return QUERY(l,u,lson(i));
        else if(l>m) return QUERY(l,u,rson(i));
        else return UNION(QUERY(l,m,lson(i)),QUERY(m+1,u,rson(i)));
    }
    
    int inline CHECK(int u,int v)
    {
        int tpu=top[u],tpv=top[v];
        state su,sv;
        memset(su.s,0,sizeof(su.s));
        memset(sv.s,0,sizeof(sv.s));
        while(tpu!=tpv)
        {
            if(dep[tpu]<dep[tpv])
            {
                swap(u,v);
                swap(tpu,tpv);
                swap(su,sv);
            }
            su=UNION(QUERY(tid[tpu],tid[u],1),su);
            u=fa[tpu];
            tpu=top[u];
        }
        if(dep[u]<dep[v])
        {
            swap(u,v);
            swap(su,sv);
        }
        su=UNION(QUERY(tid[v],tid[u],1),su);
        swap(su.s[1],su.s[2]); //关键!最后是su、sv左侧相接 
        su=UNION(su,sv);
        return su.s[0];
    }
    
    void inline CHANGE(int u,int v,int val)
    {
        int tpu=top[u],tpv=top[v];
        while(tpu!=tpv)
        {
            if(dep[tpu]<dep[tpv])
            {
                swap(u,v);
                swap(tpu,tpv);
            }
            UPDATE(tid[tpu],tid[u],val,1);
            u=fa[tpu];
            tpu=top[u];
        }
        if(dep[u]>dep[v])
        {
            swap(u,v);
        }
        UPDATE(tid[u],tid[v],val,1);
    }
    
    
    int main()
    {
        int N,M,R;
        int k,a,b,c;
        
        scanf("%d",&N);
        R=N/2;
        for(int i=1;i<=N;i++)
        {
            scanf("%d",&nw0[i]);
        }
        for(int i=1;i<N;i++)
        {
            scanf("%d%d",&a,&b);
            ADD_EDGE(a,b);
        }
        
        siz[0]=0;
        fa[R]=R; dep[R]=0; nw0[R]=nw1[R]=0;
        memset(son,0,sizeof(son));
        DFS(R);
        
        CONNECT(R,R);
        
        BUILD(1,tidc,1);
        
        scanf("%d",&M);
        while(M--)
        {
            scanf("%d%d%d",&k,&a,&b);
            if(k==1)printf("%d ",CHECK(a,b));
            else
            {
                scanf("%d",&c);
                CHANGE(a,b,c);
            }
        }
        printf("\n");
        
        return 0;
    }
    
  • 0
    @ 2016-02-04 10:24:00

    此题工作量巨大,倒不是因为树链剖分难写,而是因为栈溢出难调。前者花了一个小时;后者调了六个小时,总共用小号交了20遍才过。尝试过手动调大栈空间,结果被编译器忽略;精简递归的变量数,最终也是徒劳;差点要手写栈、改递归为循环了。

    再此忠告后三个点 RE 或 TLE (不知道为什么有时RE也会报成TLE) 的同道中人,只需要把树根定义成
    numVertex / 2 即可有效减少递归层数,以防爆栈。

    说句题外话。由上述做法可推知,后三个点的数据接近链状,而且估计从树根到叶节点的编号是递增的,所以取个中位数作树根,就把树高减半了。出题人还算比较良心,没把点的序号打乱,否则真的只能rand一个根节点了:)

  • 0
    @ 2015-10-29 17:57:10

    树链剖分+线段树维护
    没学过的先学一下树链剖分
    每次用线段树查询出到top里的最优子序列以及一些奇怪的东西(这个区间从左往右的最大值 从右往左的最大值和总和)
    记得标记不能用0 ,中间可能会修改到0

    #include <cstdio>
    #include <algorithm>
    using namespace std;
    const int N=100010,INF=2099999999;
    struct node {
    int lmax,rmax,max,sum,lazy,l,r;
    node(){lmax=rmax=max=sum=0;lazy=-INF;l=r=0;}
    }T[4*N];
    int edge[2*N],pre[2*N],now[N],tail,fa[N],depth[N],size[N],son[N],loc[N],nodeid[N],cnt,v[N],top[N],n,m,num;

    void add(int u,int v){
    edge[++tail]=v;pre[tail]=now[u];now[u]=tail;
    edge[++tail]=u;pre[tail]=now[v];now[v]=tail;
    }

    void dfs(int a){
    size[a]=1;
    for(int i=now[a];i;i=pre[i]){
    int to=edge[i];
    if(to!=fa[a]){
    depth[to]=depth[a]+1;fa[to]=a;
    dfs(to);
    size[a]+=size[to];
    if(size[to]>size[son[a]]) son[a]=to;
    }
    }
    }

    void dfs2(int a,int t){
    loc[a]=++cnt;nodeid[cnt]=a;top[a]=t;
    if(son[a]) dfs2(son[a],t);
    for(int i=now[a];i;i=pre[i]) if(edge[i]!=fa[a] && edge[i]!= son[a]) dfs2(edge[i],edge[i]);
    }

    node merge(node a,node b){//a为左 b为右 返回合并后的区间
    node t;
    t.lmax=max(a.lmax,a.sum+b.lmax);
    t.rmax=max(b.rmax,b.sum+a.rmax);
    t.sum=a.sum+b.sum;
    t.max=max(a.max,b.max);
    t.max=max(t.max,a.rmax+b.lmax);
    return t;
    }

    void up(int x){
    T[x].lmax=max(T[x<<1].lmax,T[x<<1].sum+T[x<<1|1].lmax);
    T[x].rmax=max(T[x<<1|1].rmax,T[x<<1|1].sum+T[x<<1].rmax);
    T[x].sum=T[x<<1].sum+T[x<<1|1].sum;
    T[x].max=max(T[x<<1].max,T[x<<1|1].max);
    T[x].max=max(T[x].max,T[x<<1].rmax+T[x<<1|1].lmax);
    }
    void down(int x){
    if(T[x].lazy==-INF) return;
    T[x<<1].lazy=T[x<<1|1].lazy=T[x].lazy;//这句话忘记打然后调试了一天TAT
    T[x<<1].sum=(T[x<<1].r-T[x<<1].l+1)*T[x].lazy;
    T[x<<1|1].sum=(T[x<<1|1].r-T[x<<1|1].l+1)*T[x].lazy;
    if(T[x].lazy>=0){
    T[x<<1].lmax=T[x<<1].max=T[x<<1].rmax=T[x<<1].sum;
    T[x<<1|1].lmax=T[x<<1|1].max=T[x<<1|1].rmax=T[x<<1|1].sum;
    }else{
    T[x<<1].lmax=T[x<<1].max=T[x<<1].rmax=0;
    T[x<<1|1].lmax=T[x<<1|1].max=T[x<<1|1].rmax=0;
    }
    T[x].lazy=-INF;
    }
    void build(int x,int l,int r){
    T[x].l=l;T[x].r=r;
    if(l==r) {
    T[x].lmax=T[x].rmax=T[x].max=v[nodeid[l]]>=0? v[nodeid[l]]:0;
    T[x].sum=v[nodeid[l]];return;}
    int mid=(l+r)>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
    up(x);
    }
    void change(int x,int l,int r,int L,int R,int d){
    if(l<=L && R<=r){
    T[x].sum=(T[x].r-T[x].l+1)*d;T[x].lazy=d;
    T[x].max=T[x].lmax=T[x].rmax=d>=0?T[x].sum:0;
    return;
    }
    int mid=(L+R)>>1;
    down(x);
    if(l>mid) change(x<<1|1,l,r,mid+1,R,d);
    else if(r<=mid) change(x<<1,l,r,L,mid,d);
    else change(x<<1,l,mid,L,mid,d),change(x<<1|1,mid+1,r,mid+1,R,d);
    up(x);
    }

    node ask(int x,int l,int r,int L,int R){
    if(l<=L && R<=r) return T[x];
    int mid=(L+R)>>1;
    down(x);
    if(l>mid) return ask(x<<1|1,l,r,mid+1,R);
    else if(r<=mid) return ask(x<<1,l,r,L,mid);
    else return merge(ask(x<<1,l,mid,L,mid),ask(x<<1|1,mid+1,r,mid+1,R));
    }

    int query(int u,int v){
    node disu,disv;//disu表示lca到上的信息,disv表示v到lca上的信息
    for(;top[u]!=top[v];u=fa[top[u]]){
    if(depth[top[u]]<depth[top[v]]) swap(u,v),swap(disu,disv);
    disu=merge(ask(1,loc[top[u]],loc[u],1,n),disu);
    }
    if(depth[u]<depth[v]) swap(u,v),swap(disu,disv);
    disu=merge(ask(1,loc[v],loc[u],1,n),disu);
    swap(disu.lmax,disu.rmax);
    disu=merge(disu,disv);
    return disu.max;
    }

    void modify(int u,int v,int c){
    for(;top[u]!=top[v];u=fa[top[u]]){
    if(depth[top[u]]<depth[top[v]]) swap(u,v);
    change(1,loc[top[u]],loc[u],1,n,c);
    }
    if(depth[u]<depth[v]) swap(u,v);
    change(1,loc[v],loc[u],1,n,c);
    }

    int main(){
    //freopen("1620.in","r",stdin);freopen("1620.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    for(int i=1;i<n;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    add(x,y);
    }
    dfs(1);dfs2(1,1);
    build(1,1,n);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
    int op,a,b,c;
    scanf("%d%d%d",&op,&a,&b);
    if(op==1)printf("%d ",query(a,b));
    else scanf("%d",&c),modify(a,b,c);
    }
    printf("\n");
    return 0;
    }

  • 0
    @ 2014-12-21 14:08:46

    当心爆栈的问题。。。

  • 0
    @ 2014-08-04 17:19:39

    如果你是pascal的选手,如果你想找AC程序对拍,参考甚至copy,那么就不要再往下找了,本人程序精简可读性强哦

    type
    point = record
    t,l,r,lm,rm,max,sum,same,lch,rch : longint;
    tag : boolean;
    end;
    arrayType = record
    x,y : longint;
    end;
    var
    st_cnt : longint;
    st : array[1..300000] of point;

    path_cnt : longint;
    top,path_s : array[1..100000] of longint;

    s,h,rank,belong,f,base,pos : array[0..100001] of longint;
    hash : array[1..100000] of boolean;

    e : array[1..200001] of arrayType;
    n,m,i,k,x,y,c : longint;

    function max(x,y:longint):longint;
    begin
    max := x; if y > x then exit(y);
    end;

    function max(x,y,z:longint):longint;
    begin
    max := max(max(x,y),z);
    end;

    procedure sort(l,r:longint);
    var
    i,j : longint;
    x,y : arrayType;
    begin
    i:=l;
    j:=r;
    x:=e[(l+r) div 2];
    repeat
    while (e[i].x<x.x) do inc(i);
    while (x.x<e[j].x) do dec(j);
    if not(i>j) then
    begin
    y:=e[i]; e[i]:=e[j]; e[j]:=y;
    inc(i);
    j:=j-1;
    end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
    end;

    function merge(i:longint;x,y:point):point;
    begin
    merge.t := i;
    merge.tag := false; merge.lch := x.t; merge.rch := y.t;
    merge.l := x.l; merge.r := y.r;
    merge.sum := x.sum + y.sum;
    merge.lm := max(x.lm,x.sum+y.lm);
    merge.rm := max(y.rm,y.sum+x.rm);
    merge.max := max(x.max,y.max,x.rm+y.lm);
    end;

    procedure pushtag(i,c:longint);
    begin
    st[i].tag := true; st[i].same := c; st[i].sum := (st[i].r-st[i].l+1)*c;
    if c < 0 then
    begin
    st[i].lm := c; st[i].rm := c; st[i].max := c; exit;
    end;
    st[i].lm := st[i].sum; st[i].rm := st[i].sum; st[i].max := st[i].sum;
    end;

    procedure downtag(i:longint);
    begin
    if st[i].tag then
    begin
    st[i].tag := false;
    pushtag(st[i].lch,st[i].same);
    pushtag(st[i].rch,st[i].same);
    end;
    end;

    procedure build(i,l,r:longint);
    var
    mid : longint;
    begin
    st[i].t := i; st[i].l := l; st[i].r := r; st[i].tag := false;
    if l = r then exit;
    mid := (l+r) shr 1;
    inc(st_cnt); st[i].lch := st_cnt; build(st[i].lch,l,mid);
    inc(st_cnt); st[i].rch := st_cnt; build(st[i].rch,mid+1,r);
    end;

    function ask(i,l,r:longint):point;
    var
    mid : longint;
    x,y : point;
    begin
    if (l <= st[i].l) and (st[i].r <= r) then exit(st[i]);
    mid := (st[i].l+st[i].r) shr 1;
    downtag(i);
    if l > mid then exit(ask(st[i].rch,l,r));
    if r <= mid then exit(ask(st[i].lch,l,r));
    x := ask(st[i].lch,l,r);
    y := ask(st[i].rch,l,r);
    ask := merge(1,x,y);
    end;

    procedure change(i,l,r,c:longint);
    var
    mid,lch,rch : longint;
    begin
    if (l <= st[i].l) and (st[i].r <= r) then
    begin
    pushtag(i,c);
    exit;
    end;
    mid := (st[i].l+st[i].r) shr 1;
    downtag(i);
    if l <= mid then change(st[i].lch,l,r,c);
    if r > mid then change(st[i].rch,l,r,c);
    st[i] := merge(i,st[st[i].lch],st[st[i].rch]);
    end;

    procedure query(a,b:longint);
    var
    lx,ly,lmid,ans : point;
    x,y,temp : longint;
    begin
    x := belong[a]; y:= belong[b];
    lx.lm := 0; lx.rm := 0; lx.max := 0; lx.sum := 0;
    ly.lm := 0; ly.rm := 0; ly.max := 0; ly.sum := 0;
    while x <> y do
    begin
    if h[top[x]] > h[top[y]] then
    begin
    lx := merge(1,lx,ask(x,rank[a],path_s[x]));
    a := f[top[x]];
    x := belong[a];
    end else begin
    ly := merge(1,ly,ask(y,rank[b],path_s[y]));
    b := f[top[y]];
    y := belong[b];
    end;
    end;
    if rank[a] < rank[b] then
    begin
    lmid := ask(x,rank[a],rank[b]);
    lx := merge(1,lx,lmid);
    temp := ly.lm; ly.lm := ly.rm; ly.rm := temp;
    ans := merge(1,lx,ly);
    end else begin
    lmid := ask(x,rank[b],rank[a]);
    ly := merge(1,ly,lmid);
    temp := lx.lm; lx.lm := lx.rm; lx.rm := temp;
    ans := merge(1,ly,lx);
    end;
    write(ans.max,' ');
    end;

    procedure same(a,b,c:longint);
    var
    x,y,temp : longint;
    begin
    x := belong[a]; y:= belong[b];
    while x <> y do
    begin
    if h[top[x]] > h[top[y]] then
    begin
    change(x,rank[a],path_s[x],c);
    a := f[top[x]];
    x := belong[a];
    end else begin
    change(y,rank[b],path_s[y],c);
    b := f[top[y]];
    y := belong[b];
    end;
    end;
    if h[a] < h[b] then begin temp := a; a := b; b := temp; end;
    change(x,rank[a],rank[b],c);
    end;

    procedure init(t,hi:longint);
    var
    i,maxch : longint;
    begin
    hash[t] := true; h[t] := hi; maxch := 0; s[t] := 1;
    for i := pos[t] to pos[t+1]-1 do
    begin
    if hash[e[i].y] then continue;
    f[e[i].y] := t;
    init(e[i].y,hi+1);
    inc(s[t],s[e[i].y]);
    if s[e[i].y] > s[maxch] then maxch := e[i].y;
    end;
    if maxch = 0 then
    begin
    inc(path_cnt);
    path_s[path_cnt] := 1;
    top[path_cnt] := t;
    rank[t] := 1;
    belong[t] := path_cnt; exit;
    end;
    belong[t] := belong[maxch];
    top[belong[t]] := t;
    inc(path_s[belong[t]]);
    rank[t] := rank[maxch] + 1;
    end;

    begin
    readln(n);
    for i := 1 to n do read(base[i]);
    for i := 1 to n-1 do
    begin
    readln(e[i].x,e[i].y);
    e[i+n-1].x := e[i].y; e[i+n-1].y := e[i].x;
    end;
    sort(1,(n-1) shl 1);
    for i := (n-1) shl 1 downto 1 do pos[e[i].x] := i; pos[n+1] := n shl 1-1;

    init(1,1);
    st_cnt := path_cnt;
    for i := 1 to path_cnt do build(i,1,path_s[i]);
    for i := 1 to n do same(i,i,base[i]);

    readln(m);
    for i := 1 to m do
    begin
    read(k,x,y);
    case k of
    1 : query(x,y);
    2 : begin readln(c); same(x,y,c); end;
    end;
    end;
    writeln;
    end.

  • 0
    @ 2014-08-02 22:04:21

    AC了好欢乐

  • 0
    @ 2014-02-11 19:51:17

    当我前面什么都没说,树链剖分+SGT200+行水过1Y:
    编译成功

    foo.cpp: In constructor 'state::state(int, int, int, int)':
    foo.cpp:51:26: warning: 'state::maxl' will be initialized after [-Wreorder]
    foo.cpp:51:19: warning: 'int state::maxr' [-Wreorder]
    foo.cpp:55:2: warning: when initialized here [-Wreorder]
    测试数据 #0: Accepted, time = 29 ms, mem = 36964 KiB, score = 10
    测试数据 #1: Accepted, time = 31 ms, mem = 36964 KiB, score = 10
    测试数据 #2: Accepted, time = 31 ms, mem = 36960 KiB, score = 10
    测试数据 #3: Accepted, time = 399 ms, mem = 40868 KiB, score = 10
    测试数据 #4: Accepted, time = 296 ms, mem = 40872 KiB, score = 10
    测试数据 #5: Accepted, time = 307 ms, mem = 40868 KiB, score = 10
    测试数据 #6: Accepted, time = 296 ms, mem = 40872 KiB, score = 10
    测试数据 #7: Accepted, time = 610 ms, mem = 44772 KiB, score = 10
    测试数据 #8: Accepted, time = 577 ms, mem = 44772 KiB, score = 10
    测试数据 #9: Accepted, time = 779 ms, mem = 44768 KiB, score = 10
    Accepted, time = 3355 ms, mem = 44772 KiB, score = 100

    //*****************************************************分割线***********************************************************

    #include <cstdio>
    #include <algorithm>
    #include <cstring>

    using namespace std ;

    #define AddEdge( s , t ) Add( s , t ) , Add( t , s )
    #define MAXN 100010
    #define left( t ) ( t << 1 )
    #define right( t ) ( left( t ) ^ 1 )

    struct edge {
    edge *next ;
    int t ;
    } *head[ MAXN ] ;

    void Add( int s , int t ) {
    edge *p = new( edge ) ;
    p -> t = t , p -> next = head[ s ] ;
    head[ s ] = p ;
    }

    int arr[ MAXN ] , first[ MAXN ] , child[ MAXN ] , size[ MAXN ] , h[ MAXN ] , cnt = 0 , num[ MAXN ] ;
    bool f[ MAXN ] ;
    int value[ MAXN ] , n , up[ MAXN ][ 21 ] , m ;

    void dfs0( int v ) {
    f[ v ] = false , size[ v ] = 1 , child[ v ] = 0 ;
    int ret = 0 ;
    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
    h[ p -> t ] = h[ v ] + 1 , up[ p -> t ][ 0 ] = v ;
    dfs0( p -> t ) ;
    if ( size[ p -> t ] > ret ) {
    ret = size[ p -> t ] , child[ v ] = p -> t ;
    }
    size[ v ] += size[ p -> t ] ;
    }
    }

    void dfs1( int v , int u ) {
    first[ v ] = u , f[ v ] = false , arr[ num[ v ] = ++ cnt ] = v ;
    if ( child[ v ] ) {
    dfs1( child[ v ] , u ) ;
    for ( edge *p = head[ v ] ; p ; p = p -> next ) if ( f[ p -> t ] ) {
    dfs1( p -> t , p -> t ) ;
    }
    }
    }

    struct state {
    int sum , maxs , maxr , maxl ;
    state( ) {
    sum = maxs = maxl = maxr = 0 ;
    }
    state( int _sum , int _maxs , int _maxl , int _maxr ) : sum( _sum ) , maxs( _maxs ) , maxl( _maxl ) , maxr( _maxr ) {

    }
    };

    state operator + ( const state &x , const state &y ) {
    state ret ;
    ret.sum = x.sum + y.sum ;
    ret.maxl = max( x.maxl , x.sum + y.maxl ) ;
    ret.maxr = max( y.maxr , y.sum + x.maxr ) ;
    ret.maxs = max( max( x.maxs , y.maxs ) , x.maxr + y.maxl ) ;
    return ret ;
    }

    struct node {
    int l , r , sum , maxs , maxl , maxr , v ;
    bool flag ;
    node( ) {
    sum = maxs = maxl = maxr = 0 ;
    flag = false ;
    }
    } sgt[ MAXN << 3 ] ;

    void pushdown( int t ) {
    if ( sgt[ t ].flag ) {
    sgt[ t ].sum = sgt[ t ].v * ( sgt[ t ].r - sgt[ t ].l + 1 ) ;
    sgt[ t ].maxs = sgt[ t ].maxl = sgt[ t ].maxr = sgt[ t ].v > 0 ? sgt[ t ].sum : sgt[ t ].v ;
    sgt[ t ].flag = false ;
    if ( sgt[ t ].l < sgt[ t ].r ) {
    sgt[ left( t ) ].flag = sgt[ right( t ) ].flag = true ;
    sgt[ left( t ) ].v = sgt[ right( t ) ].v = sgt[ t ].v ;
    }
    }
    }

    void update( int t ) {
    pushdown( t ) ;
    if ( sgt[ t ].l < sgt[ t ].r ) {
    pushdown( left( t ) ) , pushdown( right( t ) ) ;
    sgt[ t ].sum = sgt[ left( t ) ].sum + sgt[ right( t ) ].sum ;
    sgt[ t ].maxl = max( sgt[ left( t ) ].maxl , sgt[ left( t ) ].sum + sgt[ right( t ) ].maxl ) ;
    sgt[ t ].maxr = max( sgt[ right( t ) ].maxr , sgt[ right( t ) ].sum + sgt[ left( t ) ].maxr ) ;
    sgt[ t ].maxs = max( max( sgt[ left( t ) ].maxs , sgt[ right( t ) ].maxs ) , sgt[ left( t ) ].maxr + sgt[ right( t ) ].maxl ) ;
    }
    }

    state query( int l , int r , int t ) {
    pushdown( t ) ;
    if ( l == sgt[ t ].l && r == sgt[ t ].r ) return state( sgt[ t ].sum , sgt[ t ].maxs , sgt[ t ].maxl , sgt[ t ].maxr ) ;
    int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;
    if ( r <= mid ) return query( l , r , left( t ) ) ;
    if ( l > mid ) return query( l , r , right( t ) ) ;
    return query( l , mid , left( t ) ) + query( mid + 1 , r , right( t ) ) ;
    }

    void change( int l , int r , int v , int t ) {
    pushdown( t ) ;
    if ( sgt[ t ].l == l && r == sgt[ t ].r ) {
    sgt[ t ].flag = true , sgt[ t ].v = v ;
    pushdown( t ) ;
    return ;
    }
    int mid = ( sgt[ t ].l + sgt[ t ].r ) >> 1 ;
    if ( r <= mid ) change( l , r , v , left( t ) ) ; else
    if ( l > mid ) change( l , r , v , right( t ) ) ; else {
    change( l , mid , v , left( t ) ) , change( mid + 1 , r , v , right( t ) ) ;
    }
    update( t ) ;
    }

    void build( int l , int r , int t ) {
    sgt[ t ].l = l , sgt[ t ].r = r ;
    if ( l == r ) {
    sgt[ t ].sum = sgt[ t ].maxs = sgt[ t ].maxl = sgt[ t ].maxr = value[ arr[ l ] ] ;
    return ;
    }
    int mid = ( l + r ) >> 1 ;
    build( l , mid , left( t ) ) , build( mid + 1 , r , right( t ) ) ;
    update( t ) ;
    }

    int Lca( int u , int v ) {
    if ( h[ u ] < h[ v ] ) swap( u , v ) ;
    for ( int i = 20 ; i >= 0 ; -- i ) {
    if ( h[ up[ u ][ i ] ] >= h[ v ] ) {
    u = up[ u ][ i ] ;
    }
    }
    if ( u == v ) return u ;
    for ( int i = 20 ; i >= 0 ; -- i ) {
    if ( up[ u ][ i ] != up[ v ][ i ] ) {
    u = up[ u ][ i ] , v = up[ v ][ i ] ;
    }
    }
    return up[ u ][ 0 ] ;
    }

    state Query( int v , int u ) {
    state ret ;
    while ( h[ v ] >= h[ u ] ) {
    if ( h[ first[ v ] ] > h[ u ] ) {
    ret = query( num[ first[ v ] ] , num[ v ] , 1 ) + ret ;
    v = up[ first[ v ] ][ 0 ] ;
    } else {
    ret = query( num[ u ] , num[ v ] , 1 ) + ret ;
    break ;
    }
    }
    return ret ;
    }

    void Change( int v , int u , int c ) {
    while ( h[ v ] >= h[ u ] ) {
    if ( h[ first[ v ] ] > h[ u ] ) {
    change( num[ first[ v ] ] , num[ v ] , c , 1 ) ;
    v = up[ first[ v ] ][ 0 ] ;
    } else {
    change( num[ u ] , num[ v ] , c , 1 ) ;
    break ;
    }
    }
    }

    int main( ) {
    memset( head , 0 , sizeof( head ) ) ;
    scanf( "%d" , &n ) ;
    for ( int i = 0 ; i ++ < n ; ) scanf( "%d" , value + i ) ;
    for ( int i = 1 ; i < n ; ++ i ) {
    int s , t ; scanf( "%d%d" , &s , &t ) ;
    AddEdge( s , t ) ;
    }
    memset( f , true , sizeof( f ) ) ;
    h[ 1 ] = 1 ;
    dfs0( 1 ) ;
    memset( f , true , sizeof( f ) ) ;
    dfs1( 1 , 1 ) ;
    for ( int i = 1 ; i <= 20 ; ++ i ) {
    for ( int j = 0 ; j ++ < n ; ) {
    up[ j ][ i ] = up[ up[ j ][ i - 1 ] ][ i - 1 ] ;
    }
    }
    build( 1 , n , 1 ) ;
    scanf( "%d" , &m ) ;
    while ( m -- ) {
    int x , u , v , c ; scanf( "%d%d%d" , &x , &u , &v ) ;
    int lca = Lca( u , v ) ;
    if ( x == 1 ) {
    state l = Query( u , lca ) , r = Query( v , lca ) , M = Query( lca , lca ) ;
    int ans = max( max( l.maxs , r.maxs ) , l.maxl + r.maxl - M.sum ) ;
    printf( "%d " , ans ) ;
    } else {
    scanf( "%d" , &c ) ;
    Change( u , lca , c ) , Change( v , lca , c ) ;
    }
    }
    printf( "\n" ) ;
    return 0 ;
    }

  • 0
    @ 2013-11-04 21:13:35

    表示树链剖分一时想不出怎么写,还是乖乖码LCT吧。。。

  • 0
    @ 2013-02-27 20:07:53

    评测结果
    VijosEx via libjudge

    编译成功

    测试数据 #0: Accepted, time = 31 ms, mem = 14912 KiB, score = 10

    测试数据 #1: Accepted, time = 46 ms, mem = 14912 KiB, score = 10

    测试数据 #2: Accepted, time = 46 ms, mem = 14912 KiB, score = 10

    测试数据 #3: Accepted, time = 358 ms, mem = 15296 KiB, score = 10

    测试数据 #4: Accepted, time = 390 ms, mem = 15296 KiB, score = 10

    测试数据 #5: Accepted, time = 296 ms, mem = 15296 KiB, score = 10

    测试数据 #6: Accepted, time = 468 ms, mem = 15296 KiB, score = 10

    测试数据 #7: Accepted, time = 561 ms, mem = 15688 KiB, score = 10

    测试数据 #8: Accepted, time = 842 ms, mem = 15684 KiB, score = 10

    测试数据 #9: Accepted, time = 592 ms, mem = 15688 KiB, score = 10

    Summary: Accepted, time = 3630 ms, mem = 15688 KiB, score = 100

    {$M 10000000}
    program park;
    const inf=1000000000;
    type tree=record
    maxm,maxl,maxr,sum,lazy:longint;
    flag:boolean
    end;
    var tr:array[0..400001] of tree;
    E,pre:array[0..200001] of longint;
    ft,dep,size,link,son,w,s,top,pot:array[0..100001] of longint;
    xm,xl,xr,sum:array[1..2] of longint;
    n,m,tot,L,maxm:longint;

    function max(a,b:longint):longint;
    begin
    if a>b then max:=a else max:=b
    end;

    procedure add(a,b:longint);
    begin
    inc(L);
    E[L]:=b;
    pre[L]:=link[a];
    link[a]:=L
    end;

    procedure dfs1(x,y:longint);
    var maxi,k:longint;
    begin
    ft[x]:=y; dep[x]:=dep[y]+1; size[x]:=1;
    k:=link[x]; maxi:=0;
    while k<>0 do
    begin
    if E[k]<>ft[x] then
    begin
    dfs1(E[k],x);
    size[x]:=size[x]+size[E[k]];
    if size[E[k]]>size[maxi] then maxi:=E[k]
    end;
    k:=pre[k]
    end;
    son[x]:=maxi
    end;

    procedure dfs2(x,y:longint);
    var k:longint;
    begin
    inc(tot); pot[x]:=tot; s[tot]:=w[x]; top[x]:=y;
    if son[x]<>0 then dfs2(son[x],y);
    k:=link[x];
    while k<>0 do
    begin
    if (E[k]<>ft[x]) and (E[k]<>son[x]) then dfs2(E[k],E[k]);
    k:=pre[k]
    end
    end;

    procedure pushdown(k,L:longint);
    var lc,rc,x:longint;
    begin
    lc:=k shl 1; rc:=lc+1; x:=tr[k].lazy;
    if tr[k].lazy<0 then
    begin
    tr[lc].maxm:=x;
    tr[rc].maxm:=x;
    end
    else
    begin
    tr[lc].maxm:=x*(L-L shr 1);
    tr[rc].maxm:=x*(L shr 1)
    end;
    tr[lc].maxl:=tr[lc].maxm;
    tr[lc].maxr:=tr[lc].maxm;
    tr[rc].maxl:=tr[rc].maxm;
    tr[rc].maxr:=tr[rc].maxm;
    tr[lc].sum:=x*(L-L shr 1);
    tr[rc].sum:=x*(L shr 1);
    tr[lc].lazy:=x;
    tr[rc].lazy:=x;
    tr[lc].flag:=true;
    tr[rc].flag:=true;
    tr[k].flag:=false
    end;

    procedure update(k:longint);
    var lc,rc:longint;
    begin
    lc:=k shl 1; rc:=lc+1;
    tr[k].maxm:=max(tr[lc].maxr+tr[rc].maxl,max(tr[lc].maxm,tr[rc].maxm));
    tr[k].maxl:=max(tr[lc].maxl,tr[lc].sum+tr[rc].maxl);
    tr[k].maxr:=max(tr[rc].maxr,tr[rc].sum+tr[lc].maxr);
    tr[k].sum:=tr[lc].sum+tr[rc].sum
    end;

    procedure build(low,high,k:longint);
    var mid:longint;
    begin
    if low=high then
    begin
    tr[k].maxm:=s[low];
    tr[k].maxl:=s[low];
    tr[k].maxr:=s[low];
    tr[k].sum:=s[low];
    tr[k].flag:=false;
    exit
    end;
    mid:=(low+high) shr 1;
    build(low,mid,k shl 1);
    build(mid+1,high,k shl 1+1);
    update(k)
    end;

    procedure query(l,r,low,high,k,v:longint);
    var mid:longint;
    t1,t2,t3,t4:array[1..2] of longint;
    begin
    if (l=low) and (r=high) then
    begin
    xm[v]:=tr[k].maxm;
    xl[v]:=tr[k].maxl;
    xr[v]:=tr[k].maxr;
    sum[v]:=tr[k].sum;
    exit
    end;
    if tr[k].flag then pushdown(k,high-low+1);
    mid:=(low+high) shr 1;
    if r<=mid then
    query(l,r,low,mid,k shl 1,v)
    else
    if mid<l then
    query(l,r,mid+1,high,k shl 1+1,v)
    else
    begin
    query(l,mid,low,mid,k shl 1,v);
    t1[v]:=xm[v]; t2[v]:=xl[v]; t3[v]:=xr[v]; t4[v]:=sum[v];
    query(mid+1,r,mid+1,high,k shl 1+1,v);
    xm[v]:=max(t3[v]+xl[v],max(t1[v],xm[v]));
    xl[v]:=max(t2[v],t4[v]+xl[v]);
    xr[v]:=max(xr[v],sum[v]+t3[v]);
    sum[v]:=t4[v]+sum[v]
    end;
    update(k)
    end;

    procedure find1(x,y:longint);
    var t1,t2,t3,t4:array[1..2] of longint;
    v:longint;
    begin
    xm[1]:=-inf; xl[1]:=-inf; xr[1]:=-inf; sum[1]:=0;
    xm[2]:=-inf; xl[2]:=-inf; xr[2]:=-inf; sum[2]:=0;
    t1[1]:=-inf; t2[1]:=-inf; t3[1]:=-inf; t4[1]:=0;
    t1[2]:=-inf; t2[2]:=-inf; t3[2]:=-inf; t4[2]:=0;
    while top[x]<>top[y] do
    begin
    if dep[top[x]]>dep[top[y]] then
    begin
    query(pot[top[x]],pot[x],1,n,1,1);
    x:=ft[top[x]]; v:=1
    end
    else
    begin
    query(pot[top[y]],pot[y],1,n,1,2);
    y:=ft[top[y]]; v:=2
    end;
    xm[v]:=max(t2[v]+xr[v],max(t1[v],xm[v]));
    xl[v]:=max(xl[v],sum[v]+t2[v]);
    xr[v]:=max(t3[v],t4[v]+xr[v]);
    sum[v]:=t4[v]+sum[v];
    t1[v]:=xm[v]; t2[v]:=xl[v]; t3[v]:=xr[v]; t4[v]:=sum[v]
    end;
    if dep[x]<dep[y] then
    begin
    query(pot[x],pot[y],1,n,1,2); v:=2
    end
    else
    begin
    query(pot[y],pot[x],1,n,1,1); v:=1
    end;
    xm[v]:=max(t2[v]+xr[v],max(t1[v],xm[v]));
    xl[v]:=max(xl[v],sum[v]+t2[v]);
    xr[v]:=max(t3[v],t4[v]+xr[v]);
    sum[v]:=t4[v]+sum[v];
    if (xm[1]=-inf) or (xm[2]=-inf) then maxm:=max(xm[1],xm[2])
    else maxm:=max(xl[1]+xl[2],max(xm[1],xm[2]))
    end;

    procedure modify(l,r,x,low,high,k:longint);
    var mid:longint;
    begin
    if (l=low) and (r=high) then
    begin
    L:=high-low+1;
    if x<0 then
    begin
    tr[k].maxm:=x;
    tr[k].maxl:=x;
    tr[k].maxr:=x
    end
    else
    begin
    tr[k].maxm:=x*L;
    tr[k].maxl:=x*L;
    tr[k].maxr:=x*L
    end;
    tr[k].sum:=x*L;
    tr[k].lazy:=x;
    tr[k].flag:=true;
    exit
    end;
    if tr[k].flag then pushdown(k,high-low+1);
    mid:=(low+high) shr 1;
    if r<=mid then
    modify(l,r,x,low,mid,k shl 1)
    else
    if mid<l then
    modify(l,r,x,mid+1,high,k shl 1+1)
    else
    begin
    modify(l,mid,x,low,mid,k shl 1);
    modify(mid+1,r,x,mid+1,high,k shl 1+1)
    end;
    update(k)
    end;

    procedure find2(x,y,c:longint);
    begin
    while top[x]<>top[y] do
    if dep[top[x]]>dep[top[y]] then
    begin
    modify(pot[top[x]],pot[x],c,1,n,1);
    x:=ft[top[x]]
    end
    else
    begin
    modify(pot[top[y]],pot[y],c,1,n,1);
    y:=ft[top[y]]
    end;
    if dep[x]<dep[y] then modify(pot[x],pot[y],c,1,n,1)
    else modify(pot[y],pot[x],c,1,n,1)
    end;

    procedure init;
    var i,a,b,c,k:longint;
    begin
    L:=0; tot:=0;
    readln(n);
    for i:=1 to n do read(w[i]);
    for i:=1 to n-1 do
    begin
    readln(a,b);
    add(a,b);
    add(b,a)
    end;
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    readln(m);
    for i:=1 to m do
    begin
    read(k);
    if k=1 then
    begin
    readln(a,b);
    find1(a,b);
    if maxm<0 then write('0 ')
    else write(maxm,' ')
    end
    else
    begin
    readln(a,b,c);
    find2(a,b,c)
    end
    end
    end;

    begin
    init
    end.

  • 0
    @ 2009-09-26 15:24:54

    线段树 ,上

  • 0
    @ 2009-09-12 11:09:49

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 541ms

    ├ 测试数据 06:答案正确... 619ms

    ├ 测试数据 07:答案正确... 666ms

    ├ 测试数据 08:答案正确... 1338ms

    ├ 测试数据 09:答案正确... 1478ms

    ├ 测试数据 10:答案正确... 1525ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:6167ms

    速度比较慢,还得写非递归!~

    递归会爆栈,202错误。

  • 0
    @ 2009-08-24 08:49:43

    一开始, 总以为oimaster有一条链的数据...

    呵呵, 结果没有!

    可惜了, 第一次选错语言...不然就一次AC.

    通过此题, 发现oimaster和CQF有惊人的相似.

    CQF的棋盘上的士兵让人抓狂(我到现在还不敢写).

    oimaster的小白让我呕心沥血2天...放弃了怪盗基德比赛打代码的啊!

    就是树链剖分 + 线段树维护.

    代码很烦!300行.

    我在hi.baidu.com/boyzkk1里将会给出我的想法,

    可能的话, 我还会贴出oimaster的代码.

    //================VJ无敌bug, 状态里边的那个40分就是我的AC.

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 447ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 306ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 759ms

    ├ 测试数据 09:答案正确... 759ms

    ├ 测试数据 10:答案正确... 791ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:3062ms

  • 0
    @ 2009-08-16 14:08:39

    jzp神牛不愧是我们江苏省队的骄傲啊,目前只有他AC了!

  • 0
    @ 2009-08-16 13:56:36

    原来以为就是普通的小白加一个标记。。。

    没想到它给改成树链剖分了。。。。。

    orz

  • 0
    @ 2009-08-15 12:57:29

    Heavy-Light-Decomposition

  • 0
    @ 2009-08-14 19:36:57

    这个树链剖分是不是卡常数啊?标程都是卡过的。

    原来时限是2S啊。不好意思没有注意到。

  • 0
    @ 2009-08-14 12:24:17

    嘛是树链剖分??本人对树可是一窍不通啊!

  • 0
    @ 2009-09-09 17:20:17

    Link-cut Tree 加上Special Read可以达到这个速度:

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 462ms

    ├ 测试数据 05:答案正确... 431ms

    ├ 测试数据 06:答案正确... 431ms

    ├ 测试数据 07:答案正确... 462ms

    ├ 测试数据 08:答案正确... 1150ms

    ├ 测试数据 09:答案正确... 1134ms

    ├ 测试数据 10:答案正确... 1181ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:5251ms

    在我的电脑上加O2能到0.7s……

信息

ID
1620
难度
8
分类
树结构 | 树链剖分 点击显示
标签
(无)
递交数
769
已通过
109
通过率
14%
上传者