题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3531
题意概述：
给出一棵N个点的树，树上的每个结点有一个颜色和权值，支持以下四种操作：
1.将点x的颜色改成c。
2.将点x的权值给成w。
3.询问x->y路径上和端点相同颜色的点的权值总和（端点颜色相同）。
4.询问x->y路径上和端点相同颜色的点的权值最大值（端点颜色相同）。
分析：
首先树链剖分，每条链开C棵维护每个颜色的线段树。动态开点。
感觉没什么好说的......考试的时候灵光一闪就来了......之前还在YYlct之类的......
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
using namespace std;
const int maxn=;
const int SIZE=; int N,Q,C[maxn],W[maxn];
map<int,int>rt[maxn];
struct edge{ int to,next; }E[maxn<<];
int first[maxn],np,dep[maxn],top[maxn],fa[maxn],son[maxn],sz[maxn],len[maxn];
int lc[SIZE],rc[SIZE],sum[SIZE],mx[SIZE],np2; void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
void _scanf(char *s)
{
int cnt=;
char ch=getchar();
while(!isalpha(ch)) ch=getchar();
while(isalpha(ch)) s[cnt++]=ch,ch=getchar();
s[cnt]='\0';
}
int out_cnt,out[];
void _printf(int x)
{
out[++out_cnt]=x%,x/=;
while(x) out[++out_cnt]=x%,x/=;
while(out_cnt) putchar(''+out[out_cnt--]);
putchar('\n');
}
void add_edge(int u,int v){
E[++np]=(edge){v,first[u]};
first[u]=np;
}
void data_in()
{
_scanf(N);_scanf(Q);
for(int i=;i<=N;i++) _scanf(W[i]),_scanf(C[i]);
int x,y;
for(int i=;i<N;i++){
_scanf(x);_scanf(y);
add_edge(x,y); add_edge(y,x);
}
}
void DFS1(int i,int f,int d){
fa[i]=f,dep[i]=d,sz[i]=;
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(j==f) continue;
DFS1(j,i,d+);
sz[i]+=sz[j];
if(sz[j]>sz[son[i]]) son[i]=j;
}
}
void DFS2(int i,int f,int tp){
top[i]=tp,len[tp]++;
if(son[i]) DFS2(son[i],i,tp);
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(j==f||j==son[i]) continue;
DFS2(j,i,j);
}
}
int newnode(){
np2++,lc[np2]=rc[np2]=,sum[np2]=mx[np2]=;
return np2;
}
void pushup(int now){
mx[now]=max(mx[lc[now]],mx[rc[now]]);
sum[now]=sum[lc[now]]+sum[rc[now]];
}
void update(int &now,int L,int R,int pos,int v){
if(!now) now=newnode();
if(L==R){ sum[now]=mx[now]=v; return; }
int m=L+R>>;
if(pos<=m) update(lc[now],L,m,pos,v);
else update(rc[now],m+,R,pos,v);
pushup(now);
}
void build(int i,int f){
update(rt[top[i]][C[i]],,len[top[i]]-,dep[i]-dep[top[i]],W[i]);
for(int p=first[i];p;p=E[p].next){
if(E[p].to==f) continue;
build(E[p].to,i);
}
}
int query1(int now,int L,int R,int A,int B){
if(!now) return ;
if(A<=L&&R<=B) return sum[now];
int m=L+R>>;
if(B<=m) return query1(lc[now],L,m,A,B);
if(A>m) return query1(rc[now],m+,R,A,B);
return query1(lc[now],L,m,A,B)+query1(rc[now],m+,R,A,B);
}
int query2(int now,int L,int R,int A,int B){
if(!now) return ;
if(A<=L&&R<=B) return mx[now];
int m=L+R>>;
if(B<=m) return query2(lc[now],L,m,A,B);
if(A>m) return query2(rc[now],m+,R,A,B);
return max(query2(lc[now],L,m,A,B),query2(rc[now],m+,R,A,B));
}
int LCA(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
int query_s(int x,int y,int c){
int re=;
while(top[x]!=top[y]){
re+=query1(rt[top[x]][c],,len[top[x]]-,,dep[x]-dep[top[x]]);
x=fa[top[x]];
}
re+=query1(rt[top[x]][c],,len[top[x]]-,dep[y]-dep[top[x]],dep[x]-dep[top[x]]);
return re;
}
int query_m(int x,int y,int c){
int re=;
while(top[x]!=top[y]){
re=max(re,query2(rt[top[x]][c],,len[top[x]]-,,dep[x]-dep[top[x]]));
x=fa[top[x]];
}
re=max(re,query2(rt[top[x]][c],,len[top[x]]-,dep[y]-dep[top[x]],dep[x]-dep[top[x]]));
return re;
}
void work()
{
DFS1(,,);
DFS2(,,);
build(,);
char op[];
int x,y,z,p,c,w,ans;
for(int i=;i<=Q;i++){
_scanf(op);
if(op[]=='C'&&op[]=='C'){
_scanf(x);_scanf(c);
update(rt[top[x]][C[x]],,len[top[x]]-,dep[x]-dep[top[x]],);
update(rt[top[x]][C[x]=c],,len[top[x]]-,dep[x]-dep[top[x]],W[x]);
}
else if(op[]=='C'&&op[]=='W'){
_scanf(x);_scanf(w);
update(rt[top[x]][C[x]],,len[top[x]]-,dep[x]-dep[top[x]],W[x]=w);
}
else if(op[]=='S'){
_scanf(x);_scanf(y);
z=LCA(x,y);
_printf(query_s(x,z,C[x])+query_s(y,z,C[x])-(C[z]==C[x]?W[z]:));
}
else if(op[]=='M'){
_scanf(x);_scanf(y);
z=LCA(x,y);
_printf(max(query_m(x,z,C[x]),query_m(y,z,C[x])));
}
}
}
int main()
{
data_in();
work();
return ;
}