「题目背景」
小奇在家中的花园漫步时，总是会思考一些奇怪的问题。
「问题描述」
小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。
每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。
小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。
「输入格式」
第一行为两个整数n，q，表示温室的数目和操作的数目。
第二行有n个整数T1，T2…Tn其中Ti表示温室i中的花的种类。
接下来n-1行,每个两个整数x, y,表示温室x和y之间有一条双向道路。
接下来q行,表示q个操作,分别为以下两种形式之一:
• C x t 表示在温室x中的花的种类变为t。
• Q x y t 表示询问温室x走到温室y的路径中(包括两个端点),第t种花出现
的次数。
为了体现在线操作,输入数据中的每个操作的参数都进行了加密。记最后一次询问的答案为anslast(一开始设anslast为0),下次读入中的x,y,t均需要异或上anslast以得到真实值，在C/C++中异或为ˆ运算符，在pascal中为xor运算符。
「输出格式」
输出q行，每行一个正整数表示该次询问答案。
「样例输入」
「样例输出」
「样例解释」
加密前的操作:
Q 2 5 10
C 3 20
Q 2 5 20
C 4 20
Q 3 5 30
C 5 20
Q 2 5 20
Q 1 3 10
「数据范围」
对于30%的数据,有n <= 1000, q <= 2000。
对于50%的数据,有n <= 10000, q <= 20000。
对于100%的数据,有n <= 100000, q <= 200000，0 <= T < 2^31。
←小奇
下面的题解都是自己的话：
50%
既然强制在线，那我们就在线模拟，没什么方法，就一步步地往上找LCA并统计答案然后输出就好啦~
考场上实在没办法AC拿50分也不吃亏。
100%
有一个转化很重要。
我们可以通过类似求树上两点路径长度 dis=dep[x]+dep[y]-dep[LCA]*2 的方法，用s[i]表示从根节点到此时的i点col颜色的出现次数。
所以每次在某个节点的某个颜色出现次数增加1时，它的整个子树的每个节点的s[i]都会增加1，那么从x到y某个颜色的出现次数显然就变成 s[x]+s[y]-s[LCA]*2+val[LCA]了
那这样题目要求的单点修改、区间查询就被我们变成子树修改、单点查询了。子树修改用DFS序来看其实也就是区间修改了，可以用线段树解决。
但是颜色种类那么多怎么办呢（而且数值还那么大）？
可以用map来维护颜色编号，用动态开点线段树的方式对每一种颜色维护一棵线段树。
做本题是参考了黄学长Hzwer的题解和程序，代码可能有相似之处，但线段树的操作绝对是我自己的风格。（求资瓷~）
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map> #define For(i,a,b)for(register int i=a;i<=b;++i)
#define Dwn(i,a,b)for(register int i=a;i>=b;--i)
#define Re register
#define Pn putchar('\n') using namespace std; const int N=1e5+,Nr=1e7+;
int head[N],nxt[N*],v[N*],cnt=;
int f[N][],dfx[N],dID=,dep[N],sz[N];
int rt[N*],ls[Nr],rs[Nr],tag[Nr],tr[Nr],tID=;
int n,m,x,y,T[N*],cID=,t,Q,ans=;
map<int,int>mp;
inline void read(int &v){
v=;
char c=getchar();
while(c<''||c>'')c=getchar();
while(c>=''&&c<='')v=v*+c-'',c=getchar();
}
void write(int x){
if(x>)write(x/);
int xx=x%;
putchar(xx+'');
}
void add(int ux,int vx){
cnt++;
nxt[cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx;
cnt++;
nxt[cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux;
} void DFS(int x,int fa){
sz[x]=;
dfx[x]=++dID;
for(Re int i=head[x];i;i=nxt[i]){
int vv=v[i];
if(vv==fa)continue;
dep[vv]=dep[x]+;
f[vv][]=x;
DFS(vv,x);
sz[x]+=sz[vv];
}
} int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
Dwn(b,,)if(f[x][b]!=-){
if(dep[f[x][b]]>=dep[y])x=f[x][b];
}
if(x==y)return x;
Dwn(b,,)if(f[x][b]!=-&&f[y][b]!=-&&f[x][b]!=f[y][b]){
x=f[x][b]; y=f[y][b];
}
return f[x][];
} void pDown(int o,int l,int r){
if(!tag[o]||l==r)return;
int tg=tag[o]; tag[o]=;
if(!ls[o])ls[o]=++tID;
if(!rs[o])rs[o]=++tID;
tr[ls[o]]+=tg; tag[ls[o]]+=tg;
tr[rs[o]]+=tg; tag[rs[o]]+=tg;
} void Ins(int &o,int l,int r,int lx,int rx,int dt){
if(!o)o=++tID;
if(lx<=l&&rx>=r){
tr[o]+=dt; tag[o]+=dt;
return;
}
pDown(o,l,r);
int m=(l+r)>>;
if(lx<=m)Ins(ls[o],l,m,lx,rx,dt);
if(rx>m)Ins(rs[o],m+,r,lx,rx,dt);
} int Qry(int o,int l,int r,int px){
if(!o)return ;
if(l==r)return tr[o];
pDown(o,l,r);
int m=(l+r)>>;
if(px<=m)return Qry(ls[o],l,m,px);
else return Qry(rs[o],m+,r,px);
} int main(){
freopen("garden.in","r",stdin);
freopen("garden.out","w",stdout);
read(n); read(Q);
For(i,,n){
read(t);
if(!mp[t])mp[t]=++cID;
T[i]=mp[t];
}
For(i,,n-){
read(x); read(y);
add(x,y);
} memset(f,-,sizeof(f));
DFS(,);
For(b,,) For(i,,n){
if(f[i][b-]==-)continue;
f[i][b]=f[ f[i][b-] ][b-];
} For(i,,n){
int lx=dfx[i];
int rx=dfx[i]+sz[i]-;
Ins(rt[T[i]],,n,lx,rx,);
} For(i,,Q){ char opt=getchar();
while(opt!='C'&&opt!='Q')opt=getchar();
if(opt=='C'){
read(x); read(t);
x^=ans; t^=ans;
if(!mp[t])mp[t]=++cID;
t=mp[t];
int lx=dfx[x],rx=dfx[x]+sz[x]-; Ins(rt[T[x]],,n,lx,rx,-);
Ins(rt[t],,n,lx,rx,);
T[x]=t;
}
if(opt=='Q'){
read(x); read(y); read(t);
x^=ans; y^=ans; t^=ans;
if(!mp[t])mp[t]=++cID;
t=mp[t];
int xy=LCA(x,y);
int fn;
fn=Qry(rt[t],,n,dfx[x])+Qry(rt[t],,n,dfx[y]);
fn-=Qry(rt[t],,n,dfx[xy])*;
if(T[xy]==t)fn++;
ans=fn;
write(fn); Pn;
}
}
fclose(stdin); fclose(stdout);
return ;
}