[bzoj3531]旅行转载

对其树进行剖分，然后针对同一宗教打开一棵动态开点区间线段树，保持区间 max 和 sum 把它当做正常的树木轮廓就行了。就像正常的树木档案一样处理它。把它当做正常的树木切割就行了。就像正常的砍树一样处理它。

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 #define mid (l+r>>1) 5 struct ji{ 6 int nex,to; 7 }edge[N<<1]; 8 int E,V,n,m,x,y,r[N],w[N],c[N],head[N],fa[N],sh[N],sz[N],ma[N],top[N],id[N],ls[N40],rs[N40],f[N*40][2]; 9 char s[11]; 10 void add(int x,int y){ 11 edge[E].nex=head[x]; 12 edge[E].to=y; 13 head[x]=E++; 14 } 15 int up(int x,int y,int p){ 16 if (p)return x+y; 17 return max(x,y); 18 } 19 void update(int &k,int l,int r,int x,int y){ 20 if (!k)k=++V; 21 if (l==r){ 22 f[k][0]=f[k][1]=y; 23 return; 24 } 25 if (x<=mid)update(ls[k],l,mid,x,y); 26 else update(rs[k],mid+1,r,x,y); 27 for(int i=0;i<2;i++)f[k][i]=up(f[ls[k]][i],f[rs[k]][i],i); 28 } 29 int query(int k,int l,int r,int x,int y,int p){ 30 if ((x>r)||(l>y)||(!k))return 0; 31 if ((x<=l)&&(r<=y))return f[k][p]; 32 return up(query(ls[k],l,mid,x,y,p),query(rs[k],mid+1,r,x,y,p),p); 33 } 34 void dfs(int k,int f,int s){ 35 fa[k]=f; 36 sh[k]=s; 37 sz[k]=1; 38 for(int i=head[k];i!=-1;i=edge[i].nex) 39 if (edge[i].to!=f){ 40 dfs(edge[i].to,k,s+1); 41 sz[k]+=sz[edge[i].to]; 42 if (sz[ma[k]]<sz[edge[i].to])ma[k]=edge[i].to; 43 } 44 } 45 void dfs2(int k,int t){ 46 id[k]=++x; 47 update(r[c[k]],1,N-5,x,w[k]); 48 top[k]=t; 49 if (ma[k])dfs2(ma[k],t); 50 for(int i=head[k];i!=-1;i=edge[i].nex) 51 if ((edge[i].to!=fa[k])&&(edge[i].to!=ma[k]))dfs2(edge[i].to,edge[i].to); 52 } 53 int calc(int k,int x,int y,int p){ 54 int ans=0; 55 while (top[x]!=top[y]){ 56 if (sh[top[x]]<sh[top[y]])swap(x,y); 57 ans=up(ans,query(k,1,N-5,id[top[x]],id[x],p),p); 58 x=fa[top[x]]; 59 } 60 if (sh[x]>sh[y])swap(x,y); 61 return up(ans,query(k,1,N-5,id[x],id[y],p),p); 62 } 63 int main(){ 64 scanf("%d%d",&n,&m); 65 memset(head,-1,sizeof(head)); 66 for(int i=1;i<=n;i++)scanf("%d%d",&w[i],&c[i]); 67 for(int i=1;i<n;i++){ 68 scanf("%d%d",&x,&y); 69 add(x,y); 70 add(y,x); 71 } 72 dfs(1,1,0); 73 x=0; 74 dfs2(1,1); 75 for(int i=1;i<=m;i++){ 76 scanf("%s%d%d",s,&x,&y); 77 if (s[0]==Q){ 78 printf("%d\n",calc(r[c[x]],x,y,s[1]==S)); 79 continue; 80 } 81 if (s[1]==W)w[x]=y; 82 else{ 83 update(r[c[x]],1,N-5,id[x],0); 84 c[x]=y; 85 } 86 update(r[c[x]],1,N-5,id[x],w[x]); 87 } 88 }

View Code

转载于:https://www.cnblogs.com/PYWBKTDA/p/11249813.html