[文章目录]
Description
S国有N个城市，编号从1到N。城市间用N-1条双向道路连接，满足
从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
”CC x c”：城市x的居民全体改信了c教；
”CW x w”：城市x的评级调整为w;
”QS x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
”QM x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
从一个城市出发可以到达其它所有城市。每个城市信仰不同的宗教，如飞天面条神教、隐形独角兽教、绝地教都是常见的信仰。为了方便，我们用不同的正整数代表各种宗教， S国的居民常常旅行。旅行时他们总会走最短路，并且为了避免麻烦，只在信仰和他们相同的城市留宿。当然旅程的终点也是信仰与他相同的城市。S国政府为每个城市标定了不同的旅行评级，旅行者们常会记下途中（包括起点和终点）留宿过的城市的评级总和或最大值。
在S国的历史上常会发生以下几种事件：
”CC x c”：城市x的居民全体改信了c教；
”CW x w”：城市x的评级调整为w;
”QS x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过的城市的评级总和；
”QM x y”：一位旅行者从城市x出发，到城市y，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
啊，1A，爽。
树剖+动态开点线段树。
发现需要开n个线段树，然后每个维护的节点数的总和是n，n^2会MLE，所以动态开点。类似链表，记录lson和rson的id（下标）,然后找。区间长度的话照样是那么大，然后搜索的时候通过判断端点进入左右子树。所以说每个节点上面就有log(n)个节点为他服务,所以空间复杂度最大为nlog(n)，加上开的根节点，就大概那么大吧。
在线段树上投影的tid[]在所有线段树上都是一样的。
插入点的时候发现不存在儿子就开一个。发现修改和插入可以是一个函数，爽（suang）。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101000
#define MT 3501000
int w[N],c[N],n,m;
char st[10];
int head[N],nxt[N<<1],to[N<<1],cnt;
int root[N],tot;
int tid[N],tcnt,top[N],siz[N],son[N],fa[N],deep[N];
void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
void dfs1(int x)
{
int tmp=-1;siz[x]=1;
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x])
{
fa[to[i]]=x;deep[to[i]]=deep[x]+1;
dfs1(to[i]);
if(siz[to[i]]>tmp)
tmp=siz[to[i]],son[x]=to[i];
siz[x]+=siz[to[i]];
}
}
struct seg
{
int sum[MT],mx[MT],ls[MT],rs[MT],lch[MT],rch[MT];
void pushup(int pos)
{
sum[pos]=sum[ls[pos]]+sum[rs[pos]];
mx[pos]=max(mx[ls[pos]],mx[rs[pos]]);
}
void insert(int &pos,int l,int r,int id,int val)
{
if(!pos) pos=++tot;
if(l==id&&r==id)
{
sum[pos]=mx[pos]=val;
return ;
}
int mid=l+r>>1;
if(id<=mid) insert(ls[pos],l,mid,id,val);
else insert(rs[pos],mid+1,r,id,val);
pushup(pos);
}
int query_sum(int pos,int l,int r,int x,int y)
{
if(!pos) return 0;
if(x<=l&&y>=r) return sum[pos];
int mid=l+r>>1;
if(y<=mid) return query_sum(ls[pos],l,mid,x,y);
else if(x>mid) return query_sum(rs[pos],mid+1,r,x,y);
else return query_sum(ls[pos],l,mid,x,y)+query_sum(rs[pos],mid+1,r,x,y);
}
int query_mx(int pos,int l,int r,int x,int y)
{
if(!pos) return 0;
if(x<=l&&y>=r) return mx[pos];
int mid=l+r>>1;
if(y<=mid) return query_mx(ls[pos],l,mid,x,y);
else if(x>mid) return query_mx(rs[pos],mid+1,r,x,y);
else return max(query_mx(ls[pos],l,mid,x,y),query_mx(rs[pos],mid+1,r,x,y));
}
}T;
void dfs2(int x,int anc)
{
top[x]=anc;tid[x]=++tcnt;
T.insert(root[c[x]],1,n,tcnt,w[x]);
if(son[x]) dfs2(son[x],anc);
for(int i=head[x];i;i=nxt[i])
if(to[i]!=fa[x]&&to[i]!=son[x])
dfs2(to[i],to[i]);
}
void cc()
{
int x,y; scanf("%d%d",&x,&y);
T.insert(root[c[x]],1,n,tid[x],0);
c[x]=y;
T.insert(root[c[x]],1,n,tid[x],w[x]);
}
void cw()
{
int x,y; scanf("%d%d",&x,&y);w[x]=y;
T.insert(root[c[x]],1,n,tid[x],y);
}
void qs()
{
int x,y;scanf("%d%d",&x,&y);int id=root[c[x]],ans=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans+=T.query_sum(id,1,n,tid[top[x]],tid[x]);
x=fa[top[x]];
}
if(tid[x]>tid[y]) swap(x,y);
ans+=T.query_sum(id,1,n,tid[x],tid[y]);
printf("%d\n",ans);
}
void qm()
{
int x,y;scanf("%d%d",&x,&y);int id=root[c[x]],ans=0;
while(top[x]!=top[y])
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
ans=max(ans,T.query_mx(id,1,n,tid[top[x]],tid[x]));
x=fa[top[x]];
}
if(tid[x]>tid[y]) swap(x,y);
ans=max(ans,T.query_mx(id,1,n,tid[x],tid[y]));
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
for(int i=1;i<=n;i++) root[i]=i,T.lch[i]=1,T.rch[i]=n; tot=n;
for(int x,y,i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs1(1);dfs2(1,1);
while(m--)
{
scanf("%s",st);
switch(st[1])
{
case 'C': cc();break;
case 'W': cw();break;
case 'S': qs();break;
case 'M': qm();break;
}
}
return 0;
}