3531: [Sdoi2014]旅行
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，并记下了途中留宿过
的城市的评级最大值。
由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。 为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。
Input
输入的第一行包含整数N，Q依次表示城市数和事件数。
接下来N行，第i+l行两个整数Wi，Ci依次表示记录开始之前，城市i的
评级和信仰。
接下来N-1行每行两个整数x，y表示一条双向道路。
接下来Q行，每行一个操作，格式如上所述。
Output
对每个QS和QM事件，输出一行，表示旅行者记下的数字。
Sample Input
5 63 12 31 23 35 11 21 33 43 5QS 1 5CC 3 1QS 1 5CW 3 3QS 1 5QM 2 4
Sample Output
89113
HINT
N，Q < =10^5 ， C < =10^5
这么水的一个题一开始还想挫了。。
觉得要是跑树链剖分的话，每个点开10^5空间会出事。。、
于是考虑树上待修改莫队，10^5的5/3次方，2S肯定也过不了。。
一开始还想试一下来着。。
然后发现，其实不用每个节点开啊，我们就动态开点就好了。。
实际有用的节点很少。。
QAQ，这种水题还弄了这么就，看来我还是太菜了
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=100005;
int W[N],C[N];
int n,q;
struct qq{int x,y,last;}e[N*2];int num,last[N];
void init (int x,int y)
{num++;e[num].x=x; e[num].y=y;e[num].last=last[x];last[x]=num;
}
int dep[N],tot[N],top[N],son[N],ys[N],f[N];
void dfs (int x,int fa)
{f[x]=fa;tot[x]=1;dep[x]=dep[fa]+1;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==fa) continue;dfs(y,x);tot[x]+=tot[y];if (tot[y]>tot[son[x]]) son[x]=y;}
}
int ooo=0;
void dfs2 (int x,int tp)
{ys[x]=++ooo;top[x]=tp;if (son[x]!=0) dfs2(son[x],tp);for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (y==f[x]||y==son[x]) continue;dfs2(y,y);}
}
const int NN=N*100*2;
int s1[NN],s2[NN],c[NN],c1[NN];int lalal=0;
int root[N];
void update (int now)
{c[now]=max(c[s1[now]],c[s2[now]]);c1[now]=c1[s1[now]]+c1[s2[now]];
}
void change (int &now,int l,int r,int x,int y)//要把这个节点改为这个
{if (now==0) now=++lalal;if (l==r){c[now]=y;c1[now]=y;return ;}int mid=(l+r)>>1;if (x<=mid) change(s1[now],l,mid,x,y);else change(s2[now],mid+1,r,x,y);update(now);
}
void give (int &rt1,int &rt2,int l,int r,int x)
{if (l==r){rt2=rt1;rt1=0;return ;}if (rt2==0) rt2=++lalal;int mid=(l+r)>>1;if (x<=mid) give(s1[rt1],s1[rt2],l,mid,x);else give(s2[rt1],s2[rt2],mid+1,r,x);update(rt1);update(rt2);
}
int find (int now,int l,int r,int L,int R)
{if (now==0) return 0;if (l==L&&r==R) return c1[now];int mid=(l+r)>>1;if (R<=mid) return find(s1[now],l,mid,L,R);else if (L>mid) return find(s2[now],mid+1,r,L,R);else return find(s1[now],l,mid,L,mid)+find(s2[now],mid+1,r,mid+1,R);
}
int ans;
int solve (int x,int y,int a)//起点终点 用的线段树
//总和
{ans=0;int tx=top[x],ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}//让y来跳while (tx!=ty){ans=ans+find(root[a],1,ooo,ys[ty],ys[y]); y=f[ty];ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}}if (dep[x]>dep[y]) swap(x,y);ans=ans+find(root[a],1,ooo,ys[x],ys[y]);return ans;
}
int find1 (int now,int l,int r,int L,int R)
{if (now==0) return 0;if (l==L&&r==R) return c[now];int mid=(l+r)>>1;if (R<=mid) return find1(s1[now],l,mid,L,R);else if (L>mid) return find1(s2[now],mid+1,r,L,R);else return max(find1(s1[now],l,mid,L,mid),find1(s2[now],mid+1,r,mid+1,R));
}
int solve1 (int x,int y,int a)
{ans=0;int tx=top[x],ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}//让y来跳while (tx!=ty){//printf("%d %d %d %d\n",x,y,tx,ty);ans=max(ans,find1(root[a],1,ooo,ys[ty],ys[y])); y=f[ty];ty=top[y];if (dep[tx]>dep[ty]) {swap(x,y);swap(tx,ty);}}//printf("%d %d\n",x,y);if (dep[x]>dep[y]) swap(x,y);ans=max(ans,find1(root[a],1,ooo,ys[x],ys[y]));return ans;
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&q);for (int u=1;u<=n;u++) scanf("%d%d",&W[u],&C[u]);for (int u=1;u<n;u++){int x,y;scanf("%d%d",&x,&y);init(x,y);init(y,x);}dfs(1,0);dfs2(1,1);
/* for (int u=1;u<=n;u++)printf("%d %d %d\n",dep[u],top[u],ys[u]);*/for (int u=1;u<=n;u++) change(root[C[u]],1,ooo,ys[u],W[u]);while (q--){char ss[5];scanf("%s",ss);if (ss[1]=='C')//改信{int x,c;scanf("%d%d",&x,&c);give(root[C[x]],root[c],1,ooo,ys[x]);C[x]=c;}else if (ss[1]=='W'){int x,c;scanf("%d%d",&x,&c);change(root[C[x]],1,ooo,ys[x],c);}else if (ss[1]=='S')//评级总和 {int x,y;scanf("%d%d",&x,&y);printf("%d\n",solve(x,y,C[x]));}else{int x,y;scanf("%d%d",&x,&y);printf("%d\n",solve1(x,y,C[x]));}}return 0;
}