hdu_5221_Occupation(树剖)

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=5221

题意：给你一棵树，每个节点有一定的值，有三种操作： 1 x y 表示占领树上x-y的所有节点，2 x 表示去掉这点，3 x表示占领以这个节点为根的所有节点

题解：1 2 都是树剖操作，3则要记录树剖的时间戳，一个根节点下的点的新编号都是连续的，所以只要记录该根节点的最大时间戳就知道这个区间了

 #include<cstdio>

 #pragma comment(linker, "/STACK:102400000,102400000")

 #define F(i,a,b) for(int i=a;i<=b;i++)

 #define root 1,n,1

 #define ls l,m,rt<<1

 #define rs m+1,r,rt<<1|1

 const int N=1e5+;

 int dep[N],sz[N],hs[N],top[N],tid[N],fid[N],fa[N],idx,mp[N];

 int t,n,m,pp,x,y,a[N],sum[N*],vis[*N],ans[N*],g[N],nxt[*N],v[*N],ed;

 inline int max(int a,int b){return a>b?a:b;}

 inline void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}

 //线段树

 void build(int l,int r,int rt){

     vis[rt]=ans[rt]=;

     if(l==r){sum[rt]=a[fid[l]];return;}

     int m=(l+r)>>;

     build(ls),build(rs);

     sum[rt]=sum[rt<<]+sum[rt<<|];

 }

 inline void pd(int rt){

     if(vis[rt])

     vis[rt<<]=vis[rt<<|]=,ans[rt<<]=sum[rt<<],ans[rt<<|]=sum[rt<<|],vis[rt]=;

 }

 void update(int L,int R,int op,int l,int r,int rt){

     if(L<=l&&r<=R){

         vis[rt]=op,ans[rt]=op?sum[rt]:;

         return;

     }

     pd(rt);

     int m=(l+r)>>;

     if(L<=m)update(L,R,op,ls);

     if(R>m)update(L,R,op,rs);

     ans[rt]=ans[rt<<]+ans[rt<<|];

 }

 //树剖

 void dfs1(int u,int pre){

     dep[u]=dep[pre]+,hs[u]=,fa[u]=pre,sz[u]=;

     for(int i=g[u];i;i=nxt[i])if(v[i]!=pre)

     dfs1(v[i],u),sz[u]+=sz[v[i]],hs[u]=(sz[v[i]]>sz[hs[u]])?v[i]:hs[u];

 }

 void dfs2(int u,int tp){

     top[u]=tp,tid[u]=++idx,fid[idx]=u,mp[u]=idx;

     if(hs[u])dfs2(hs[u],tp),mp[u]=max(mp[u],mp[hs[u]]);

     for(int i=g[u];i;i=nxt[i])

     if(v[i]!=fa[u]&&v[i]!=hs[u])dfs2(v[i],v[i]),mp[u]=max(mp[u],mp[v[i]]);

 }

 void up(int x,int y){

     int fx=top[x],fy=top[y];

     while(fx!=fy){

         if(dep[fx]>dep[fy])update(tid[fx],tid[x],,root),x=fa[fx],fx=top[x];

         else update(tid[fy],tid[y],,root),y=fa[fy],fy=top[y];

     }

     if(dep[x]>dep[y])x^=y,y^=x,x^=y;

     update(tid[x],tid[y],,root);

 }

 int main(){

     scanf("%d",&t);

     while(t--){

         scanf("%d",&n);

         F(i,,n)scanf("%d",a+i);

         F(i,,n)g[i]=;ed=;

         F(i,,n-)scanf("%d%d",&x,&y),adg(x,y),adg(y,x);

         dfs1(,),idx=,dfs2(,),build(root);

         scanf("%d",&m);

         F(i,,m){

             scanf("%d",&pp);

             if(pp==)scanf("%d%d",&x,&y),up(x,y);

             else if(pp==)scanf("%d",&x),update(tid[x],tid[x],,root);

             else scanf("%d",&x),update(tid[x],mp[x],,root);

             printf("%d\n",ans[]);

         }

     }

     return ;

 }