A. 「SDOI2014」旅行
给每个宗教开一棵线段树，树剖 \(+\) 线段树单点修改区间查询即可。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
#define read(x){\
char ch;\
int fu=1;\
while(!isdigit(ch=getchar()))\
fu-=(ch=='-')<<1;\
x=ch&15;\
while(isdigit(ch=getchar()))\
x=(x<<1)+(x<<3)+(ch&15);\
x*=fu;\
}
#define int ll
#define pb push_back
using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=1e5+5,maxm=5e6+5;
int n,m,a[maxn],b[maxn],cnt;
int top[maxn],fa[maxn],dfn[maxn];
int sz[maxn],hes[maxn],dep[maxn];
vector<int> e[maxn];
il void dfs1(int u){
dep[u]=dep[fa[u]]+1;
sz[u]=1;
int mxs=0;
for(int v:e[u]){
if(v==fa[u]){
continue;
}
fa[v]=u;
dfs1(v);
sz[u]+=sz[v];
if(mxs<sz[v]){
mxs=sz[v];
hes[u]=v;
}
}
}
il void dfs2(int u){
dfn[u]=++cnt;
if(!top[u]){
top[u]=u;
}
if(hes[u]){
top[hes[u]]=top[u];
dfs2(hes[u]);
}
for(int v:e[u]){
if(v==fa[u]||v==hes[u]){
continue;
}
dfs2(v);
}
}
int rt[maxn],ls[maxm],rs[maxm];
int tot,sum[maxm],mx[maxm];
il void pushup(int id){
sum[id]=sum[ls[id]]+sum[rs[id]];
mx[id]=max(mx[ls[id]],mx[rs[id]]);
}
il void upd(int &id,int l,int r,int pos,int val){
if(!id){
id=++tot;
}
if(l==r){
sum[id]=mx[id]=val;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid){
upd(ls[id],l,mid,pos,val);
}
else{
upd(rs[id],mid+1,r,pos,val);
}
pushup(id);
}
il int qsum(int id,int L,int R,int l,int r){
if(!id){
return 0;
}
if(L>=l&&R<=r){
return sum[id];
}
int mid=(L+R)>>1,res=0;
if(l<=mid){
res+=qsum(ls[id],L,mid,l,r);
}
if(r>mid){
res+=qsum(rs[id],mid+1,R,l,r);
}
return res;
}
il int qmx(int id,int L,int R,int l,int r){
if(!id){
return 0;
}
if(L>=l&&R<=r){
return mx[id];
}
int mid=(L+R)>>1,res=0;
if(l<=mid){
res=max(res,qmx(ls[id],L,mid,l,r));
}
if(r>mid){
res=max(res,qmx(rs[id],mid+1,R,l,r));
}
return res;
}
namespace cplx{
bool end;
il double usdmem(){return (&begin-&end)/10485796.0;}
}
signed main(){
read(n)read(m);
for(int i=1;i<=n;i++){
read(a[i])read(b[i]);
}
for(int i=1,u,v;i<n;i++){
read(u)read(v);
e[u].pb(v),e[v].pb(u);
}
dfs1(1),dfs2(1);
for(int i=1;i<=n;i++){
upd(rt[b[i]],1,n,dfn[i],a[i]);
}
while(m--){
char opt[5];
int u,v;
scanf(" %s",opt+1);
read(u)read(v);
switch(opt[2]){
case 'C':{
upd(rt[b[u]],1,n,dfn[u],0);
b[u]=v;
upd(rt[b[u]],1,n,dfn[u],a[u]);
break;
}
case 'W':{
a[u]=v;
upd(rt[b[u]],1,n,dfn[u],a[u]);
break;
}
case 'S':{
int res=0,x=b[u];
while(top[u]!=top[v]){
// puts("666");
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
res+=qsum(rt[x],1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
res+=qsum(rt[x],1,n,dfn[u],dfn[v]);
printf("%lld\n",res);
break;
}
default:{
int res=0,x=b[u];
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]){
swap(u,v);
}
res=max(res,qmx(rt[x],1,n,dfn[top[u]],dfn[u]));
u=fa[top[u]];
}
if(dep[u]>dep[v]){
swap(u,v);
}
res=max(res,qmx(rt[x],1,n,dfn[u],dfn[v]));
printf("%lld\n",res);
break;
}
}
}
return 0;
}
}
signed main(){return asbt::main();}