学了学动态开点的树链剖分，其实跟动态开点的线段树差不多啦
查询的时候别ssbb地动态开点，如果没这个点果断返回0就行
只要注意花的种类能到intmax就行qwq！！！！
#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<cstdlib> #include<map> #define mid ((l+r)>>1) #define maxn 100010 #define check(x) if(x==0) x=++tot; using namespace std; inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f; } int tot; map<int,int> root; int ls[maxn*100]; int rs[maxn*100]; int q[maxn]; int size[maxn]; int top[maxn]; int son[maxn]; int father[maxn]; int dfn[maxn]; int deep[maxn]; int back[maxn],cnt; int n,m; struct Edge{ int next,to; }edge[maxn*3]; int head[maxn],num; inline void add(int from,int to){ edge[++num]=(Edge){head[from],to}; head[from]=num; } void find(int x,int fa){ size[x]=1; deep[x]=deep[fa]+1; for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(to==fa) continue; father[to]=x; find(to,x); size[x]+=size[to]; if(son[x]==0||size[son[x]]<size[to]) son[x]=to; } } void unionn(int x,int Top){ top[x]=Top; dfn[x]=++cnt; back[cnt]=x; if(son[x]==0) return; unionn(son[x],Top); for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(to==father[x]||to==son[x]) continue; unionn(to,to); } return; } inline void pushup(int rt){ tree[rt]=tree[ls[rt]]+tree[rs[rt]]; } void update(int o,int num,int l,int r,int &rt){ check(rt); if(l==r){ tree[rt]+=num; return; } if(o<=mid) update(o,num,l,mid,ls[rt]); else update(o,num,mid+1,r,rs[rt]); pushup(rt); } int query(int from,int to,int l,int r,int &rt){ if(rt==0) return 0; if(from<=l&&to>=r) return tree[rt]; int ans=0; if(from<=mid) ans+=query(from,to,l,mid,ls[rt]); if(to>mid) ans+=query(from,to,mid+1,r,rs[rt]); return ans; } inline void addcol(int pos,int val){ update(dfn[pos],-1,1,n,root[q[pos]]); update(dfn[pos],1,1,n,root[val]); q[pos]=val; } int ask(int from,int to,int val){ int ans=0; while(top[from]!=top[to]){ if(deep[top[from]]<deep[top[to]]) swap(from,to); ans+=query(dfn[top[from]],dfn[from],1,n,root[val]); from=father[top[from]]; } if(deep[from]>deep[to]) swap(from,to); ans+=query(dfn[from],dfn[to],1,n,root[val]); return ans; } int main(){ n=read(),m=read(); for(int i=1;i<=n;++i) q[i]=read(); for(int i=1;i<n;++i){ int from=read(),to=read(); add(from,to); add(to,from); } find(1,1); unionn(1,1); for(int i=1;i<=n;++i) update(dfn[i],1,1,n,root[q[i]]); int last=0; for(int i=1;i<=m;++i){ char c[10];int x,y; scanf("%s",c); if(c[0]=='C'){ x=read()^last,y=read()^last; addcol(x,y); } else{ x=read()^last,y=read()^last; int z=read()^last; last=ask(x,y,z); printf("%d ",last); } } return 0; }