首页 > 代码库 > bzoj3639: Query on a tree VII
bzoj3639: Query on a tree VII
Description
Each node has a color, white or black, and a weight.
We will ask you to perfrom some instructions of the following form:
- 0 u : ask for the maximum weight among the nodes which are connected to u, two nodes are connected iff all the node on the path from u to v (inclusive u and v) have a same color.
- 1 u : toggle the color of u(that is, from black to white, or from white to black).
- 2 u w: change the weight of u to w.
Input
The first line contains a number n denoted how many nodes in the tree(1 ≤ n ≤ 105). The next n - 1 lines, each line has two numbers (u, v) describe a edge of the tree(1 ≤ u, v ≤ n).
The next 2 lines, each line contains n number, the first line is the initial color of each node(0 or 1), and the second line is the initial weight, let‘s say Wi, of each node(|Wi| ≤ 109).
The next line contains a number m denoted how many operations we are going to process(1 ≤ m ≤ 105). The next m lines, each line describe a operation (t, u) as we mentioned above(0 ≤ t ≤ 2, 1 ≤ u ≤ n, |w| ≤ 109).
Output
For each query operation, output the corresponding result.
对原树每个点x，另外拆出两个新点代表黑白，x和x的所有子节点连边到对应的新点，这时重构后得到的树上每个连通块颜色相同，且每次颜色修改只会断开两条边再连上两条边
然后可以用平衡树维护森林的括号序列，时间复杂度O((n+m)logn)
#include<cstdio>#define G *++ptrconst int N=100007;char buf[N*100],*ptr=buf-1;int _(){ int x=0,c=G,f=1; while(c<48)c==‘-‘&&(f=-1),c=G; while(c>47)x=x*10+c-48,c=G; return x*f;}int ch[N*6][5],n;int col[N];#define lc ch][0#define rc ch][1#define fa ch][2#define val ch][3#define mxv ch][4int max(int a,int b){return a>b?a:b;}void up(int x){ x[mxv]=max(x[val],max(x[lc][mxv],x[rc][mxv]));}void rot(int x){ int f=x[fa],g=f[fa],d=(x!=f[lc]); if(g)g[ch][g[lc]!=f]=x; x[fa]=g; (f[ch][d]=x[ch][d^1])[fa]=f; (x[ch][d^1]=f)[fa]=x; up(f),up(x);}void sp(int x,int y=0){ while(x[fa]!=y){ int f=x[fa]; if(f[fa]!=y)rot((f[lc]==x)==(f[fa][lc]==f)?f:x); rot(x); }}int gl(int x){ sp(x); while(x[lc])x=x[lc]; sp(x); return x;}void lk(int x,int y){ sp(x);sp(y); int z=y[rc],xr=x+n*3; (y[rc]=x)[fa]=y; up(y); sp(xr); (xr[rc]=z)[fa]=xr; up(xr);}void ct(int x){ int xr=x+n*3; sp(x); int l=x[lc]; l[fa]=x[lc]=0; up(x); sp(xr); int r=xr[rc]; r[fa]=xr[rc]=0; up(xr); r=gl(r); (r[lc]=l)[fa]=r; up(r);}int F(int w,int t){ return w+(t+1)*n;}void init(){ const int inf=0x3f3f3f3f; 0[val]=0[mxv]=-inf; for(int i=1;i<=n;++i)col[i]=_(); for(int i=1;i<=n;++i)i[val]=i[mxv]=_(); for(int i=n+1;i<=n*6;++i)i[val]=i[mxv]=-inf; for(int i=1;i<=n*3;++i)(i[rc]=i+n*3)[fa]=i,up(i);}#undef faint es[N*2],enx[N*2],e0[N],ep=2;int fa[N],sz[N],son[N],dep[N],top[N];void f1(int w,int pa){ sz[w]=1; dep[w]=dep[fa[w]=pa]+1; lk(F(w,col[w]),w); for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=pa){ f1(u,w); lk(u,F(w,col[u])); sz[w]+=sz[u]; if(sz[u]>sz[son[w]])son[w]=u; } }}void f2(int w,int tp){ top[w]=tp; if(son[w])f2(son[w],tp); for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=fa[w]&&u!=son[w])f2(u,u); }}int up(int x,int y){ int a=top[x],b=top[y]; while(a!=b){ x=fa[a]; if(x==y)return a; a=top[x]; } return son[y];}int main(){ fread(buf,1,sizeof(buf),stdin)[buf]=0; n=_(); for(int i=1,a,b;i<n;++i){ a=_();b=_(); es[ep]=b;enx[ep]=e0[a];e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];e0[b]=ep++; } init(); f1(1,0);f2(1,1); for(int q=_();q;--q){ int o=_(),w=_(); if(o==0){ int l=gl(w); if(l>n)w=up(w,(l-1)%n+1); else w=1; sp(w); sp(w+n*3,w); printf("%d\n",max(w[val],(w+n*3)[lc][mxv])); }else if(o==1){ ct(F(w,col[w])); lk(F(w,col[w]^1),w); if(w!=1){ int f=fa[w]; ct(w); lk(w,F(f,col[w]^1)); } col[w]^=1; }else{ sp(w); w[val]=_(); up(w); } } return 0;}
bzoj3639: Query on a tree VII