题目链接：戳我
真激动。。我这等蒟蒻竟然竟然A了数据结构题
树剖+动态开点线段树
就是给每一个信仰建立一颗线段树。。然后发现空间开不下，就动态开点qwqwq，具体我觉得还是看代码更详细。。。。
代码如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define MAXN 100010
#define inf 0x3f3f3f3f
using namespace std;
int n,m,tt,tot,cnt;
int w[MAXN],c[MAXN],head[MAXN<<1],rt[MAXN<<5];
int dfn[MAXN],siz[MAXN],son[MAXN],fa[MAXN],dep[MAXN],id[MAXN],top[MAXN];
char s[10];
struct Node{int ls,rs,sum,maxx;}t[MAXN<<5];
struct Edge{int nxt,to,dis;}edge[MAXN<<1];
inline void add(int from,int to){edge[++tt].nxt=head[from],edge[tt].to=to,head[from]=tt;}
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void dfs1(int x,int pre)
{
fa[x]=pre;
dep[x]=dep[pre]+1;
siz[x]=1;
int maxx=-1;
for(int i=head[x];i;i=edge[i].nxt)
{
int v=edge[i].to;
if(v==pre) continue;
dfs1(v,x);
siz[x]+=siz[v];
if(siz[v]>maxx) maxx=siz[v],son[x]=v;
}
}
inline void dfs2(int x,int topf)
{
top[x]=topf;
id[x]=++tot;
if(son[x]) dfs2(son[x],topf);
for(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);
}
}
inline void push_up(int x)
{
t[x].maxx=max(t[t[x].ls].maxx,t[t[x].rs].maxx);
t[x].sum=t[t[x].ls].sum+t[t[x].rs].sum;
}
inline void update(int &x,int l,int r,int pos,int k)
{
if(!x) x=++cnt;
if(l==r) {t[x].maxx=t[x].sum=k;return;}
int mid=(l+r)>>1;
if(pos<=mid) update(t[x].ls,l,mid,pos,k);
else update(t[x].rs,mid+1,r,pos,k);
push_up(x);
}
inline int query_sum(int x,int l,int r,int ll,int rr)
{
int cur_ans=0;
if(ll<=l&&r<=rr) return t[x].sum;
int mid=(l+r)>>1;
if(ll<=mid&&t[x].ls) cur_ans+=query_sum(t[x].ls,l,mid,ll,rr);
if(mid<rr&&t[x].rs) cur_ans+=query_sum(t[x].rs,mid+1,r,ll,rr);
return cur_ans;
}
inline int query_max(int x,int l,int r,int ll,int rr)
{
if(ll<=l&&r<=rr) return t[x].maxx;
int mid=(l+r)>>1,cur_ans=-inf;
if(ll<=mid&&t[x].ls) cur_ans=max(cur_ans,query_max(t[x].ls,l,mid,ll,rr));
if(mid<rr&&t[x].rs) cur_ans=max(cur_ans,query_max(t[x].rs,mid+1,r,ll,rr));
return cur_ans;
}
inline int QUE_SUM(int k,int x,int y)
{
int cur_ans=0;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
cur_ans+=query_sum(rt[k],1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
cur_ans+=query_sum(rt[k],1,n,id[y],id[x]);
return cur_ans;
}
inline int QUE_MAX(int k,int x,int y)
{
int cur_ans=-inf;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]]) swap(x,y);
cur_ans=max(cur_ans,query_max(rt[k],1,n,id[top[x]],id[x]));
x=fa[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
cur_ans=max(cur_ans,query_max(rt[k],1,n,id[y],id[x]));
return cur_ans;
}
inline void print(int x,int l,int r)
{
if(l==r)
{
printf("x=%d pos=%d sum=%d maxx=%d
",x,l,t[x].sum,t[x].maxx);
return;
}
int mid=(l+r)>>1;
if(t[x].ls) print(t[x].ls,l,mid);
if(t[x].rs) print(t[x].rs,mid+1,r);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("ce.in","r",stdin);
#endif
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);//w评级 c信仰
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
}
dfs1(1,1);
dfs2(1,1);
for(int i=1;i<=n;i++) update(rt[c[i]],1,n,id[i],w[i]);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%s%d%d",s,&x,&y);
if(s[1]=='S') //询问评级总和
{
printf("%d
",QUE_SUM(c[x],x,y));
}
else if(s[1]=='M') //询问最大值
{
printf("%d
",QUE_MAX(c[x],x,y));
}
else if(s[1]=='C')//城市x改信y教
{
update(rt[c[x]],1,n,id[x],0);
update(rt[y],1,n,id[x],w[x]);
c[x]=y;
}
else //城市x评级调整为y
{
update(rt[c[x]],1,n,id[x],y);
w[x]=y;
}
// print(rt[1],1,n);puts("");
// print(rt[2],1,n);puts("");
// print(rt[3],1,n);puts("");
}
return 0;
}