题目大意:给出一个n个点的数,和m次操作。每个点有颜色和权值。 每次操作分4种 1:修改一个点的颜色 2:修改一个点的权值 3:询问从x到y的路径上,和x相同颜色的点的权值和(保证x,y同颜色) 4:询问从x到y的路径上,和x相同颜色的点的权值最大值(保证x,y同颜色)
思路:树链剖分,用线段树来维护和以及最大值。
代码:
#include<cstdio>
#include<iostream>
#define M 3000009
using namespace std;
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];
void ins(int x,int y)
{
to[++cnt]=y,next[cnt]=head[x],head[x]=cnt;
}
void dfs1(int x)
{
size[x]=1;
for (int i=head[x];i;i=next[i])
if (pa[x]!=to[i])
{
deep[to[i]]=deep[x]+1,pa[to[i]]=x;
dfs1(to[i]),size[x]+=size[to[i]];
}
}
void dfs2(int x,int chain)
{
int i,k=0;
id[x]=++dfn,top[x]=chain;
for (i=head[x];i;i=next[i])
if (deep[to[i]]>deep[x] && size[to[i]]>size[k]) k=to[i];
if (!k) return; dfs2(k,chain);
for (i=head[x];i;i=next[i])
if (pa[x]!=to[i] && k!=to[i]) dfs2(to[i],to[i]);
}
void up_date(int k)
{
sum[k]=sum[lc[k]]+sum[rc[k]];
mx[k]=max(mx[lc[k]],mx[rc[k]]);
}
void change(int &cur,int l,int r,int x,int val)
{
if (!cur) cur=++num;
if (l==r) { sum[cur]=mx[cur]=val; return; }
int mid=l+r>>1;
if (x<=mid) change(lc[cur],l,mid,x,val);
else change(rc[cur],mid+1,r,x,val);
up_date(cur);
}
int ask_sum(int cur,int L,int R,int l,int r)
{
if (!cur) return 0;
if (L==l && R==r) return sum[cur];
int mid=L+R>>1;
if (r<=mid) return ask_sum(lc[cur],L,mid,l,r);
if (l>mid) return ask_sum(rc[cur],mid+1,R,l,r);
return ask_sum(lc[cur],L,mid,l,mid)+ask_sum(rc[cur],mid+1,R,mid+1,r);
}
int ask_max(int cur,int L,int R,int l,int r)
{
if (!cur) return 0;
if (L==l && R==r) return mx[cur];
int mid=L+R>>1;
if (r<=mid) return ask_max(lc[cur],L,mid,l,r);
if (l>mid) return ask_max(rc[cur],mid+1,R,l,r);
return max(ask_max(lc[cur],L,mid,l,mid),ask_max(rc[cur],mid+1,R,mid+1,r));
}
int Ask_Sum(int x,int y,int z)
{
int ans=0;
for (;top[x]!=top[y];x=pa[top[x]])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=ask_sum(root[z],1,n,id[top[x]],id[x]);
}
if (deep[x]>deep[y]) swap(x,y);
return ans+ask_sum(root[z],1,n,id[x],id[y]);
}
int Ask_Max(int x,int y,int z)
{
int ans=-10000000;
for (;top[x]!=top[y];x=pa[top[x]])
{
if (deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,ask_max(root[z],1,n,id[top[x]],id[x]));
}
if (deep[x]>deep[y]) swap(x,y);
return max(ans,ask_max(root[z],1,n,id[x],id[y]));
}
int main()
{
scanf("%d%d",&n,&m);
int i,x,y;
for (i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
for (i=1;i<n;i++) scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
dfs1(1),dfs2(1,1);
for (i=1;i<=n;i++) change(root[c[i]],1,n,id[i],w[i]);
for (i=1;i<=m;i++)
{
char ch[9];
scanf("%s%d%d",ch,&x,&y);
if (ch[0]=='C')
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;
else change(root[c[x]],1,n,id[x],y),w[x]=y;
else if (ch[1]=='S') printf("%d\n",Ask_Sum(x,y,c[x]));
else printf("%d\n",Ask_Max(x,y,c[x]));
}scanf("%d",&n);
return 0;
}