题解：
对于每一种宗教都维护一棵线段树，每次在对应的线段树上查询和与最大值即可。修改的话同样如此。剩下便是树剖干的事情。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
struct node{
int nxt,to;
}edge[maxn*2];
int head[maxn];
int n,q;
int x,y;
struct node1{
int rc,lc;
long long maxx,sum;
}tree[maxn*21];
int root[maxn];
int faith[maxn];
int level[maxn];
char opt[666];
int cnt;
void add(int x,int y){
edge[++cnt].nxt=head[x];
edge[cnt].to=y;
head[x]=cnt;
}
int dep[maxn],fa[maxn],siz[maxn],son[maxn];
void dfs1(int x,int f){
dep[x]=dep[f]+1;
fa[x]=f;
siz[x]=1;
int maxson=-1;
for(register int i=head[x];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[x]) continue;
dfs1(v,x);
siz[x]+=siz[v];
if(siz[v]>maxson){
maxson=siz[v];
son[x]=v;
}
}
}
int top[maxn],id[maxn],in;
void dfs2(int x,int topf){
top[x]=topf;
id[x]=++in;
if(!son[x]) return;
dfs2(son[x],topf);
for(register int i=head[x];i;i=edge[i].nxt){
int v=edge[i].to;
if(v==fa[x]||v==son[x]) continue;
dfs2(v,v);
}
}
int tot;
void build(int &rt,int l,int r,int v,int pos){
if(!rt) rt=++tot;
if(l==pos&&pos==r){
tree[rt].maxx=v;
tree[rt].sum=v;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) build(tree[rt].lc,l,mid,v,pos);
else build(tree[rt].rc,mid+1,r,v,pos);
tree[rt].maxx=max(tree[tree[rt].lc].maxx,tree[tree[rt].rc].maxx);
tree[rt].sum=tree[tree[rt].lc].sum+tree[tree[rt].rc].sum;
}
void clear(int rt){
tree[rt].lc=0;
tree[rt].rc=0;
tree[rt].maxx=0;
tree[rt].sum=0;
}
void del(int &rt,int l,int r,int pos){
if(l==r){
clear(rt);
rt=0;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) del(tree[rt].lc,l,mid,pos);
else del(tree[rt].rc,mid+1,r,pos);
tree[rt].maxx=max(tree[tree[rt].lc].maxx,tree[tree[rt].rc].maxx);
tree[rt].sum=tree[tree[rt].lc].sum+tree[tree[rt].rc].sum;
if(!tree[rt].rc&&!tree[rt].lc){
clear(rt);
rt=0;
}
}
long long querymax(int rt,int l,int r,int l1,int r1){
if(!rt) return 0;
if(l>=l1&&r<=r1) return tree[rt].maxx;
int mid=(l+r)>>1;
long long ans=0;
if(l1<=mid) ans=max(ans,querymax(tree[rt].lc,l,mid,l1,r1));
if(r1>mid) ans=max(ans,querymax(tree[rt].rc,mid+1,r,l1,r1));
return ans;
}
long long querysum(int rt,int l,int r,int l1,int r1){
if(!rt) return 0;
if(l>=l1&&r<=r1) return tree[rt].sum;
int mid=(l+r)>>1;
long long ans=0;
if(l1<=mid) ans+=querysum(tree[rt].lc,l,mid,l1,r1);
if(r1>mid) ans+=querysum(tree[rt].rc,mid+1,r,l1,r1);
return ans;
}
long long linkmax(int x,int y){
int start=faith[x];
long long ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans=max(ans,querymax(root[start],1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
ans=max(ans,querymax(root[start],1,n,id[y],id[x]));
return ans;
}
long long linksum(int x,int y){
int start=faith[x];
long long ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
ans+=querysum(root[start],1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
ans+=querysum(root[start],1,n,id[y],id[x]);
return ans;
}
void linkup1(int x,int y){
level[x]=y;
build(root[faith[x]],1,n,level[x],id[x]);
}
void linkup2(int x,int y){
del(root[faith[x]],1,n,id[x]);
faith[x]=y;
build(root[faith[x]],1,n,level[x],id[x]);
}
int main(){
scanf("%d%d",&n,&q);
for(register int i=1;i<=n;i++) scanf("%d%d",&level[i],&faith[i]);
for(register int i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(register int i=1;i<=n;i++) build(root[faith[i]],1,n,level[i],id[i]);
for(register int i=1;i<=q;i++){
scanf("%s",opt);
scanf("%d%d",&x,&y);
if(opt[0]=='C'){
if(opt[1]=='C') linkup2(x,y);
else linkup1(x,y);
}
if(opt[0]=='Q'){
if(opt[1]=='M') printf("%lld\n",linkmax(x,y));
else printf("%lld\n",linksum(x,y));
}
}
return 0;
}
View Code