题目大意：
给出一个n个点的树，和m次操作。每个点有颜色和权值。 每次操作分4种 1：修改一个点的颜色 2：修改一个点的权值 3：询问从x到y的路径上，和x相同颜色的点的权值和（保证x，y同颜色） 4：询问从x到y的路径上，和x相同颜色的点的权值最大值（保证x，y同颜色）
思路：
树链剖分，用线段树来维护和以及最大值。
代码：
1 #include<cstdio> 2 #include<iostream> 3 #define M 3000009 4 using namespace std; 5 6 int cnt,dfn,num,n,m,w[M],c[M],to[M<<1],next[M<<1],head[M],deep[M],size[M],pa[M],id[M],top[M],root[M],sum[M<<2],mx[M<<2],lc[M<<2],rc[M<<2]; 7 8 void ins(int x,int y) 9 { 10 to[++cnt]=y,next[cnt]=head[x],head[x]=cnt; 11 } 12 13 void dfs1(int x) 14 { 15 size[x]=1; 16 for (int i=head[x];i;i=next[i]) 17 if (pa[x]!=to[i]) 18 { 19 deep[to[i]]=deep[x]+1,pa[to[i]]=x; 20 dfs1(to[i]),size[x]+=size[to[i]]; 21 } 22 } 23 24 void dfs2(int x,int chain) 25 { 26 int i,k=0; 27 id[x]=++dfn,top[x]=chain; 28 for (i=head[x];i;i=next[i]) 29 if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i]; 30 if (!k) return; dfs2(k,chain); 31 for (i=head[x];i;i=next[i]) 32 if (pa[x]!=to[i] && k!=to[i]) dfs2(to[i],to[i]); 33 } 34 35 void up_date(int k) 36 { 37 sum[k]=sum[lc[k]]+sum[rc[k]]; 38 mx[k]=max(mx[lc[k]],mx[rc[k]]); 39 } 40 41 void change(int &cur,int l,int r,int x,int val) 42 { 43 if (!cur) cur=++num; 44 if (l==r) { sum[cur]=mx[cur]=val; return; } 45 int mid=l+r>>1; 46 if (x<=mid) change(lc[cur],l,mid,x,val); 47 else change(rc[cur],mid+1,r,x,val); 48 up_date(cur); 49 } 50 51 int ask_sum(int cur,int L,int R,int l,int r) 52 { 53 if (!cur) return 0; 54 if (L==l && R==r) return sum[cur]; 55 int mid=L+R>>1; 56 if (r<=mid) return ask_sum(lc[cur],L,mid,l,r); 57 if (l>mid) return ask_sum(rc[cur],mid+1,R,l,r); 58 return ask_sum(lc[cur],L,mid,l,mid)+ask_sum(rc[cur],mid+1,R,mid+1,r); 59 } 60 61 int ask_max(int cur,int L,int R,int l,int r) 62 { 63 if (!cur) return 0; 64 if (L==l && R==r) return mx[cur]; 65 int mid=L+R>>1; 66 if (r<=mid) return ask_max(lc[cur],L,mid,l,r); 67 if (l>mid) return ask_max(rc[cur],mid+1,R,l,r); 68 return max(ask_max(lc[cur],L,mid,l,mid),ask_max(rc[cur],mid+1,R,mid+1,r)); 69 } 70 71 int Ask_Sum(int x,int y,int z) 72 { 73 int ans=0; 74 for (;top[x]!=top[y];x=pa[top[x]]) 75 { 76 if (deep[top[x]]<deep[top[y]]) swap(x,y); 77 ans+=ask_sum(root[z],1,n,id[top[x]],id[x]); 78 } 79 if (deep[x]>deep[y]) swap(x,y); 80 return ans+ask_sum(root[z],1,n,id[x],id[y]); 81 } 82 83 int Ask_Max(int x,int y,int z) 84 { 85 int ans=-10000000; 86 for (;top[x]!=top[y];x=pa[top[x]]) 87 { 88 if (deep[top[x]]<deep[top[y]]) swap(x,y); 89 ans=max(ans,ask_max(root[z],1,n,id[top[x]],id[x])); 90 } 91 if (deep[x]>deep[y]) swap(x,y); 92 return max(ans,ask_max(root[z],1,n,id[x],id[y])); 93 } 94 95 int main() 96 { 97 scanf("%d%d",&n,&m); 98 int i,x,y; 99 for (i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); 100 for (i=1;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x); 101 dfs1(1),dfs2(1,1); 102 for (i=1;i<=n;i++) change(root[c[i]],1,n,id[i],w[i]); 103 for (i=1;i<=m;i++) 104 { 105 char ch[9]; 106 scanf("%s%d%d",ch,&x,&y); 107 if (ch[0]=='C') 108 if (ch[1]=='C') change(root[c[x]],1,n,id[x],0),change(root[y],1,n,id[x],w[x]),c[x]=y; 109 else change(root[c[x]],1,n,id[x],y),w[x]=y; 110 else if (ch[1]=='S') printf("%d\n",Ask_Sum(x,y,c[x])); 111 else printf("%d\n",Ask_Max(x,y,c[x])); 112 }scanf("%d",&n); 113 return 0; 114 }
转载于:https://www.cnblogs.com/HHshy/p/5823383.html
