Query on The Trees(hdu 4010)

题意：

　　给出一颗树，有4种操作：

1、如果x和y不在同一棵树上则在xy连边

2、如果x和y在同一棵树上并且x!=y则把x换为树根并把y和y的父亲分离

3、如果x和y在同一棵树上则x到y的路径上所有的点权值+w

4、如果x和y在同一棵树上则输出x到y路径上的最大值

/*
  本来一道很水的LCT，结果hdu的提交页面被我刷屏了。。。
  还是too young too simple啊，刚开始不知道多组数据，提交了N次，然后又因为下面的赋值问题提交了N++次。 
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 300010
#define inf 1000000000
using namespace std;
int fa[N],son[N][2],x[N],y[N],val[N],mx[N],tag[N],rev[N],st[N],n,m;
void pushdown(int x){
    int l=son[x][0],r=son[x][1];
    if(rev[x]){
        swap(son[x][0],son[x][1]);
        rev[l]^=1;rev[r]^=1;rev[x]^=1;
    }
    if(tag[x]){
        if(l){tag[l]+=tag[x];val[l]+=tag[x];mx[l]+=tag[x];}
        if(r){tag[r]+=tag[x];val[r]+=tag[x];mx[r]+=tag[x];}
        tag[x]=0;
    }
}
void pushup(int x){
    int l=son[x][0],r=son[x][1];
    mx[x]=max(val[x],max(mx[l],mx[r]));
}
bool isroot(int x){
    return son[fa[x]][0]!=x&&son[fa[x]][1]!=x; 
}
void rotate(int x){
    int y=fa[x],z=fa[y],l,r;
    if(son[y][0]==x)l=0;else l=1;r=l^1;
    if(!isroot(y)){
        if(son[z][0]==y) son[z][0]=x;
        else son[z][1]=x;
    }
    fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
    son[y][l]=son[x][r];son[x][r]=y;
    pushup(y);pushup(x);
}
void splay(int x){
    int top=0;st[++top]=x;
    for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];
    for(int i=top;i;i--) pushdown(st[i]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if(son[z][0]==y^son[y][0]==x)rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
}
void access(int x){
    int t=0;
    while(x){
        splay(x);
        son[x][1]=t;
        pushup(x);
        t=x;x=fa[x];
    }
}
void makeroot(int x){
    access(x);
    splay(x);
    rev[x]^=1;
}
void join(int x,int y){
    makeroot(x);
    fa[x]=y;
}
void cut(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
    //fa[son[y][0]]=son[y][0]=0;
    //我可能学了假的c++，连从右到左赋值都不知道！！！ 
    son[y][0]=fa[son[y][0]]=0;
    pushup(y);
}
int find(int x){
    access(x);splay(x);
    int y=x;
    while(son[y][0]) y=son[y][0];
    return y;
}
void work(){
    mx[0]=-inf;
    for(int i=1;i<n;i++)scanf("%d%d",&x[i],&y[i]);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]),mx[i]=val[i];
    for(int i=1;i<n;i++)join(x[i],y[i]);
    scanf("%d",&m);
    int opt,x,y,w;
    for(int i=1;i<=m;i++){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d",&x,&y);
            if(find(x)==find(y)){printf("-1
");continue;}
            join(x,y);
        }
        else if(opt==2){
            scanf("%d%d",&x,&y);
            if(find(x)!=find(y)||x==y){printf("-1
");continue;}
            cut(x,y);
        }
        else if(opt==3){
            scanf("%d%d%d",&w,&x,&y);
            if(find(x)!=find(y)){printf("-1
");continue;}
            makeroot(x);access(y);splay(y);
            val[y]+=w;tag[y]+=w;mx[y]+=w;
        }
        else {
            scanf("%d%d",&x,&y);
            if(find(x)!=find(y)){printf("-1
");continue;}
            makeroot(x);access(y);splay(y);
            printf("%d
",mx[y]);
        }
    }
    printf("
");
}
int main(){
    while(scanf("%d",&n)!=EOF){
        memset(fa,0,sizeof(fa));
        memset(son,0,sizeof(son));
        memset(val,0,sizeof(val));
        memset(mx,0,sizeof(mx));
        memset(tag,0,sizeof(tag));
        memset(rev,0,sizeof(rev));
        work();
    }
    return 0;
}

Query on The Trees(hdu 4010)

相关推荐