题意
一棵树，每个节点有权值和信仰值。旅行时只在与起点信仰相同的节点停留，并获得权值。有如下操作：
- 单点修改信仰值
- 单点修改权值
- 查询 $(x,y)$ 路径上权值和
- 查询 $(x,y)$ 路径上权值最大值
其中节点数 $N\le 100000$ ，操作数 $M\le 100000$ ，宗教个数 $C\le 100000$ 。
题解
显然每个宗教需要单独维护，但每个宗教开个线段树空间要爆，所以用动态开点线段树。
剩下就板子了，看注释吧。
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
char ch=getchar();
int f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge {
int next,to;
} edge[200005];
struct Tree {
int lson,rson,sum,mx;
} tree[2400005];
int cnt,head[100005],n,m,a,b,tcnt,rt[100005],c[100005];
int dfsord,siz[100005],fa[100005],son[100005],deep[100005],top[100005],id[100005],w[100005],ord[100005];
inline void add(int u,int v)
{
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
}
inline void pushup(int x)
{
tree[x].sum=tree[tree[x].lson].sum+tree[tree[x].rson].sum;
tree[x].mx=max(tree[tree[x].lson].mx,tree[tree[x].rson].mx);
}
void update(int &x,int s,int l,int r,int delta) //修改
{
if (!x) x=++tcnt;
if (r-l==1) tree[x].sum=tree[x].mx=delta;
else
{
int mid=(l+r)>>1;
if (s<mid) update(tree[x].lson,s,l,mid,delta);
else update(tree[x].rson,s,mid,r,delta);
pushup(x);
}
}
void del(int &x,int s,int l,int r) //删除
{
if (!x) return;
if (r-l==1) tree[x].sum=tree[x].mx=0;
else
{
int mid=(l+r)>>1;
if (s<mid) del(tree[x].lson,s,l,mid);
else del(tree[x].rson,s,mid,r);
pushup(x);
}
}
int qSum(int x,int l,int r,int tl,int tr) //线段树查询权值和
{
if (!x) return 0;
if (l<=tl && r>=tr) return tree[x].sum;
else
{
int mid=(tl+tr)>>1,ans=0;
if (l<mid) ans+=qSum(tree[x].lson,l,r,tl,mid);
if (r>mid) ans+=qSum(tree[x].rson,l,r,mid,tr);
return ans;
}
}
int qMax(int x,int l,int r,int tl,int tr) //线段树查询最大值
{
if (!x) return 0;
if (l<=tl && r>=tr) return tree[x].mx;
else
{
int mid=(tl+tr)>>1,ans=0;
if (l<mid) ans=max(ans,qMax(tree[x].lson,l,r,tl,mid));
if (r>mid) ans=max(ans,qMax(tree[x].rson,l,r,mid,tr));
return ans;
}
}
void dfs1(int x,int f,int dep) //树剖第一次dfs
{
fa[x]=f;
deep[x]=dep;
siz[x]=1;
int mx=0;
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==f) continue;
dfs1(y,x,dep+1);
siz[x]+=siz[y];
if (siz[y]>mx)
{
mx=siz[y];
son[x]=y;
}
}
}
void dfs2(int x,int topf) //树剖第二次dfs
{
top[x]=topf;
id[x]=++dfsord;
ord[dfsord]=x;
if (!son[x]) return;
dfs2(son[x],topf);
for (int i=head[x];i;i=edge[i].next)
{
int y=edge[i].to;
if (y==fa[x] || y==son[x]) continue;
dfs2(y,y);
}
}
inline int qRangeSum(int u,int v,int rel) //树上查询权值和
{
int ans=0;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ans+=qSum(rt[rel],id[top[u]],id[u]+1,1,n+1);
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
ans+=qSum(rt[rel],id[u],id[v]+1,1,n+1);
return ans;
}
inline int qRangeMax(int u,int v,int rel) //树上查询权值最大值
{
int ans=0;
while (top[u]!=top[v])
{
if (deep[top[u]]<deep[top[v]]) swap(u,v);
ans=max(ans,qMax(rt[rel],id[top[u]],id[u]+1,1,n+1));
u=fa[top[u]];
}
if (deep[u]>deep[v]) swap(u,v);
ans=max(ans,qMax(rt[rel],id[u],id[v]+1,1,n+1));
return ans;
}
int main()
{
n=read(); m=read();
for (int i=1;i<=n;i++) w[i]=read(),c[i]=read();
for (int i=1;i<n;i++)
{
a=read(); b=read();
add(a,b);
add(b,a);
}
dfs1(1,0,1);
dfs2(1,1);
for (int i=1;i<=n;i++) update(rt[c[ord[i]]],i,1,n+1,w[ord[i]]); //建树
while (m--)
{
char ch[2]; scanf("%s",ch); a=read(); b=read();
if (ch[1]=='C') //修改宗教
{
del(rt[c[a]],id[a],1,n+1); //先删除
c[a]=b;
update(rt[c[a]],id[a],1,n+1,w[a]); //再添加
}
else if (ch[1]=='W')
{
del(rt[c[a]],id[a],1,n+1);
w[a]=b;
update(rt[c[a]],id[a],1,n+1,w[a]);
}
else if (ch[1]=='S') printf("%d\n",qRangeSum(a,b,c[a]));
else printf("%d\n",qRangeMax(a,b,c[a]));
}
return 0;
}