%%%Manchery
先考虑没有深度限制，要计算子树中不同的颜色的个数，就令所有节点的初始权值为1，就把两两相同颜色的节点的LCA的权值-1，然后求一遍子树权值和就可以了。 但是这样做复杂度是 O(n2) ，而且会在某个节点多次-1。其实只要把颜色相同的节点提出来，按照dfs序的标号排个序，然后在相邻的节点的LCA处-1就行了。
然后考虑有深度限制，仔细想想发现这个限制特别像主席树，那么就以深度排序，以深度为时间点建主席树，那么上面说的对节点修改的操作也要在这个时候做，可以用set维护……
#include <cstdio> #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <set> #define N 100010 using namespace std; typedef pair<int,int> pairs; typedef set<pairs>::iterator itr; int n,m,t,cnt,g,Ans; int G[N],A[N],dpt[N],L[N],R[N],w[N],p[N],rt[N]; int fa[N][25]; set<pairs> c[N]; struct edge{ int t,nx; }E[N<<2]; struct tree{ int l,r,ls,rs,sum; }T[N*100]; inline void reaD(int &x){ char c=getchar(); x=0; for(;c>57||c<48;c=getchar());for(;c>=48&&c<=57;x=x*10+c-48,c=getchar()); } inline void Insert(int x,int y){ E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt; } void dfs(int x,int f){ dpt[x]=dpt[f]+1; fa[x][0]=f; L[x]=++g; for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=G[x];i;i=E[i].nx) dfs(E[i].t,x); R[x]=++g; } inline int LCA(int x,int y){ if(dpt[x]<dpt[y]) return LCA(y,x); for(int i=20;~i;i--) if(dpt[fa[x][i]]>=dpt[y]) x=fa[x][i]; if(x==y) return x; for(int i=20;~i;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; return fa[x][0]; } inline bool cmp(int a,int b){ return dpt[a]<dpt[b]; } void Insert(int x0,int &x1,int y,int w,int l,int r){ x1=++cnt; T[x1].l=l; T[x1].r=r; T[x1].ls=T[x0].ls; T[x1].rs=T[x0].rs; T[x1].sum=T[x0].sum+w; if(l==r) return; int mid=l+r>>1; if(y<=mid) Insert(T[x0].ls,T[x1].ls,y,w,l,mid); else Insert(T[x0].rs,T[x1].rs,y,w,mid+1,r); } int query(int x,int l,int r){ if(!x) return 0; if(T[x].l==l&&T[x].r==r) return T[x].sum; int mid=T[x].l+T[x].r>>1; if(r<=mid) return query(T[x].ls,l,r); if(l>mid) return query(T[x].rs,l,r); return query(T[x].ls,l,mid)+query(T[x].rs,mid+1,r); } void build(int &x,int l,int r){ x=++cnt; T[x].l=l; T[x].r=r; T[x].sum=0; if(l==r) return ; int mid=l+r>>1; build(T[x].ls,l,mid); build(T[x].rs,mid+1,r); } int main(){ reaD(t); while(t--){ reaD(n); reaD(m); memset(G,0,sizeof(G)); cnt=g=0; dpt[1]=1; for(int i=1;i<=n;i++) reaD(A[i]),c[i].clear(); for(int i=2,u;i<=n;i++) reaD(u),Insert(u,i); dfs(1,0); for(int i=1;i<=n;i++) p[i]=i; sort(p+1,p+1+n,cmp); cnt=0; rt[1]=0; build(rt[1],1,g); Insert(rt[1],rt[1],L[p[1]],1,1,g); c[A[1]].insert(pairs(L[1],1)); for(int i=2;i<=n;i++){ int v=p[i],u=p[i-1]; Insert(rt[dpt[u]],rt[dpt[v]],L[v],1,1,g); if(c[A[v]].empty()) c[A[v]].insert(pairs(L[v],v)); else{ c[A[v]].insert(pairs(L[v],v)); itr a=c[A[v]].find(pairs(L[v],v)); itr y=--a,x; a=c[A[v]].find(pairs(L[v],v)); x=++a; if(x!=c[A[v]].end()&&y!=c[A[v]].end()) Insert(rt[dpt[v]],rt[dpt[v]],L[LCA(x->second,y->second)],1,1,g); if(x!=c[A[v]].end()) Insert(rt[dpt[v]],rt[dpt[v]],L[LCA(x->second,v)],-1,1,g); if(y!=c[A[v]].end()) Insert(rt[dpt[v]],rt[dpt[v]],L[LCA(y->second,v)],-1,1,g); } } Ans=0; for(int i=1,u,v;i<=m;i++){ reaD(u); reaD(v); u^=Ans; v^=Ans; printf("%d\n",Ans=query(rt[min(dpt[u]+v,dpt[p[n]])],L[u],R[u])); } } }