题目：洛谷3313、BZOJ3531。
题目大意：
给你一棵树，每个点有一个分类和一个值。
有四种操作：
1. 修改某个点的分类
2. 修改某个点的值
3. 查询两个分类相同的点的最短路上，与这两个点分类相同的所有点的值的和
4. 查询两个分类相同的点的最短路上，与这两个点分类相同的所有点的值的最大值
解题思路：
树链剖分。
给每个分类建一棵线段树维护。
内存不够怎么办？
动态开点即可。我用了指针+内存池大法。
C++ Code：
#include<bits/stdc++.h>
#define N 100005
int n,q,w[N],c[N],cnt=0,head[N],son[N],dep[N],fa[N],sz[N],top[N],dfn[N],idx=0,tp=0;
char opt[5];
struct node{
node *ld,*rd;
int sum,max;
}P[5000001],*STK[5000001];
inline node* newnode(){
node* p=STK[tp--];
p->ld=p->rd=NULL;
p->sum=0;p->max=-0x3f3f3f3f;
return p;
}
inline void delnode(node*& rt){
STK[++tp]=rt;
rt=NULL;
}
class SegmentTree{
private:
int val,id,L,R;
void ADD(node*& rt,int l,int r){
if(rt==NULL)rt=newnode();
if(l==r)rt->sum=rt->max=val;else{
int mid=(l+r)>>1;
if(id<=mid)ADD(rt->ld,l,mid);else
ADD(rt->rd,mid+1,r);
int sum=0,max=-0x3f3f3f3f;
if(rt->ld!=NULL)sum=rt->ld->sum,max=rt->ld->max;
if(rt->rd!=NULL){
sum+=rt->rd->sum;
int x=rt->rd->max;
if(max<x)max=x;
}
rt->sum=sum,rt->max=max;
}
}
void DEL(node*& rt,int l,int r){
if(l==r){
val=rt->sum;
delnode(rt);
return;
}
int mid=(l+r)>>1;
if(id<=mid)DEL(rt->ld,l,mid);else
DEL(rt->rd,mid+1,r);
int sum=0,max=-0x3f3f3f3f;
if(rt->ld!=NULL)sum=rt->ld->sum,max=rt->ld->max;
if(rt->rd!=NULL){
sum+=rt->rd->sum;
int x=rt->rd->max;
if(max<x)max=x;
}
rt->sum=sum,rt->max=max;
}
void qs(node* rt,int l,int r){
if(rt==NULL)return;
if(L<=l&&r<=R){
val+=rt->sum;
return;
}
int mid=(l+r)>>1;
if(L<=mid)qs(rt->ld,l,mid);
if(mid<R)qs(rt->rd,mid+1,r);
}
void qm(node* rt,int l,int r){
if(rt==NULL)return;
if(L<=l&&r<=R){
if(val<rt->max)val=rt->max;
return;
}
int mid=(l+r)>>1;
if(L<=mid)qm(rt->ld,l,mid);
if(mid<R)qm(rt->rd,mid+1,r);
}
public:
node* rt;
inline void init(){rt=newnode();}
void modify(int num,int value){
val=value;
id=num;
ADD(rt,1,n);
}
int deletenode(int num){
id=num;
DEL(rt,1,n);
return val;
}
int query_sum(int x,int y){
int ans=0;
for(;top[x]!=top[y];)
if(dep[top[x]]>=dep[top[y]]){
L=dfn[top[x]],R=dfn[x];
val=0;
qs(rt,1,n);
ans+=val;
x=fa[top[x]];
}else{
L=dfn[top[y]],R=dfn[y];
val=0;
qs(rt,1,n);
ans+=val;
y=fa[top[y]];
}
if(dep[x]<=dep[y]){
L=dfn[x],R=dfn[y];
val=0;
qs(rt,1,n);
ans+=val;
}else{
L=dfn[y],R=dfn[x];
val=0;
qs(rt,1,n);
ans+=val;
}
return ans;
}
int query_max(int x,int y){
int ans=-0x3f3f3f3f;
for(;top[x]!=top[y];)
if(dep[top[x]]>=dep[top[y]]){
L=dfn[top[x]],R=dfn[x];
val=-0x3f3f3f3f;
qm(rt,1,n);
if(val>ans)ans=val;
x=fa[top[x]];
}else{
L=dfn[top[y]],R=dfn[y];
val=-0x3f3f3f3f;
qm(rt,1,n);
if(val>ans)ans=val;
y=fa[top[y]];
}
if(dep[x]<=dep[y]){
L=dfn[x],R=dfn[y];
val=-0x3f3f3f3f;
qm(rt,1,n);
if(val>ans)ans=val;
}else{
L=dfn[y],R=dfn[x];
val=-0x3f3f3f3f;
qm(rt,1,n);
if(val>ans)ans=val;
}
return ans;
}
}tree[N];
inline int readint(){
int c=getchar(),d=0;
for(;!isdigit(c);c=getchar());
for(;isdigit(c);c=getchar())d=(d<<3)+(d<<1)+(c^'0');
return d;
}
struct edge{
int to,nxt;
}e[N<<1];
void dfs(int now){
son[now]=0;
sz[now]=1;
for(int i=head[now];i;i=e[i].nxt)
if(!dep[e[i].to]){
dep[e[i].to]=dep[now]+1;
fa[e[i].to]=now;
dfs(e[i].to);
sz[now]+=sz[e[i].to];
if(!son[now]||sz[son[now]]<sz[e[i].to])son[now]=e[i].to;
}
}
void dfs2(int now){
dfn[now]=++idx;
if(son[now])top[son[now]]=top[now],dfs2(son[now]);
for(int i=head[now];i;i=e[i].nxt)
if(dep[now]<dep[e[i].to]&&e[i].to-son[now])dfs2(top[e[i].to]=e[i].to);
}
inline void memory_init(){
for(int i=0;i<5000001;++i)
STK[i]=&P[i];
tp=5000000;
}
int main(){
memory_init();
for(int i=1;i<N;++i)tree[i].init();
n=readint(),q=readint();
for(int i=1;i<=n;++i)w[i]=readint(),c[i]=readint();
memset(head,0,sizeof head);
for(int i=1;i<n;++i){
int u=readint(),v=readint();
e[++cnt]=(edge){v,head[u]};
head[u]=cnt;
e[++cnt]=(edge){u,head[v]};
head[v]=cnt;
}
memset(dep,0,sizeof dep);
memset(fa,-1,sizeof fa);
memset(top,0,sizeof top);
fa[dep[1]=top[1]=1]=0;
dfs(1);dfs2(1);
for(int i=1;i<=n;++i)tree[c[i]].modify(dfn[i],w[i]);
while(q--){
scanf("%s",opt);
if(opt[0]=='C'){
if(opt[1]=='C'){
int x=readint(),c=readint();
tree[c].modify(dfn[x],tree[::c[x]].deletenode(dfn[x]));
::c[x]=c;
}else{
int x=readint(),w=readint();
tree[c[x]].modify(dfn[x],w);
}
}else{
if(opt[1]=='S'){
int x=readint(),y=readint();
printf("%d
",tree[c[x]].query_sum(x,y));
}else{
int x=readint(),y=readint();
printf("%d
",tree[c[x]].query_max(x,y));
}
}
}
return 0;
}