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，并记下了途中留宿过

的城市的评级最大值。

由于年代久远，旅行者记下的数字已经遗失了，但记录开始之前每座城市的信仰与评级，还有事件记录本身是完好的。请根据这些信息，还原旅行者记下的数字。    为了方便，我们认为事件之间的间隔足够长，以致在任意一次旅行中，所有城市的评级和信仰保持不变。

Solution

只需要对每个宗教建一棵线段树就好啦

#include
     
      #include
      
       #include
       
        #include
        
         #define MAXN 100005using namespace std;int n,q,w[MAXN],c[MAXN],head[MAXN],cnt=0;int father[MAXN],top[MAXN],maxv[MAXN],siz[MAXN],deep[MAXN],pos[MAXN],sz=0;int tot=0,rt[MAXN],ls[MAXN*100],rs[MAXN*100],maxn[MAXN*100],sum[MAXN*100];int read(){    int x=0,f=1;char c=getchar();    while(c<'0'||c>'9'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct Node1{    int next,to;}Edges[MAXN*2];void addedge(int u,int v){    Edges[++cnt].next=head[u];    head[u]=cnt;    Edges[cnt].to=v;}void dfs1(int u){    siz[u]=1;    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==father[u])continue;        father[v]=u,deep[v]=deep[u]+1;        dfs1(v);        siz[u]+=siz[v];        if(siz[v]>siz[maxv[u]])maxv[u]=v;    }}void dfs2(int u,int t){    top[u]=t;    ++sz,pos[u]=sz;    if(maxv[u])dfs2(maxv[u],t);    for(int i=head[u];~i;i=Edges[i].next)    {        int v=Edges[i].to;        if(v==maxv[u]||v==father[u])continue;        dfs2(v,v);    }}void update(int idx){    sum[idx]=sum[ls[idx]]+sum[rs[idx]];    maxn[idx]=max(maxn[ls[idx]],maxn[rs[idx]]);}void change(int &idx,int l,int r,int p,int w){    if(!idx)++tot,idx=tot;    if(l==r){maxn[idx]=sum[idx]=w;return;}    int mid=(l+r)>>1;    if(p<=mid)change(ls[idx],l,mid,p,w);    else change(rs[idx],mid+1,r,p,w);    update(idx);}int querysum(int idx,int l,int r,int L,int R){    if(!idx)return 0;    if(L==l&&R==r)return sum[idx];    int mid=(l+r)>>1;    if(R<=mid)return querysum(ls[idx],l,mid,L,R);    else if(L>mid)return querysum(rs[idx],mid+1,r,L,R);    else return querysum(ls[idx],l,mid,L,mid)+querysum(rs[idx],mid+1,r,mid+1,R);}int querymax(int idx,int l,int r,int L,int R){    if(!idx)return 0;    if(L==l&&R==r)return maxn[idx];    int mid=(l+r)>>1;    if(R<=mid)return querymax(ls[idx],l,mid,L,R);    else if(L>mid)return querymax(rs[idx],mid+1,r,L,R);    else return max(querymax(ls[idx],l,mid,L,mid),querymax(rs[idx],mid+1,r,mid+1,R));}int QS(int x,int y){    int t=c[x],res=0;    while(top[x]!=top[y])    {        if(deep[top[x]]