感谢带我飞的rxd大爷
我们先考虑不管深度限制可修改我们怎么做
就是把每种颜色按照dfs序排列 然后给这些点都+1 但是相邻两个的lca处要-1 这样子树不同颜色数就是子树和
然后我们把深度限制 看做按照深度的顺序加点 加点我们需要维护什么 每种颜色的序列 这个用set或平衡树 在序列中插入 我们对前驱后继lca什么瞎处理一通 然后记一下这个版本 也就是在主席树上修改
然后一个深度限制 就相当于到那个深度版本的线段树中询问子树和
#include<cstdio> #include<cstdlib> #include<algorithm> #include<set> using namespace std; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=500005; const int K=25; int root[N]; int ls[K*N],rs[K*N],sum[K*N]; int ncnt; inline void Modify(int &y,int x,int l,int r,int t,int a){ y=++ncnt; int mid=(l+r)>>1; if (l==r){ sum[y]=sum[x]+a; return; } if (t<=mid) rs[y]=rs[x],Modify(ls[y],ls[x],l,mid,t,a),sum[y]=sum[ls[y]]+sum[rs[y]]; else ls[y]=ls[x],Modify(rs[y],rs[x],mid+1,r,t,a),sum[y]=sum[ls[y]]+sum[rs[y]]; } inline int Query(int x,int l,int r,int ql,int qr){ if (!x) return 0; if (ql<=l && r<=qr) return sum[x]; int mid=(l+r)>>1,ret=0; if (ql<=mid) ret+=Query(ls[x],l,mid,ql,qr); if (qr>mid) ret+=Query(rs[x],mid+1,r,ql,qr); return ret; } struct edge{ int u,v,next; }G[N<<1]; int head[N],inum; inline void add(int u,int v,int p){ G[p].u=u; G[p].v=v; G[p].next=head[u]; head[u]=p; } #define V G[p].v int clk; int fat[N][K],depth[N]; int pre[N],size[N],back[N]; inline void dfs(int u,int fa){ size[u]=1; pre[u]=++clk; back[clk]=u; fat[u][0]=fa; depth[u]=depth[fa]+1; for (int k=1;k<=20;k++) fat[u][k]=fat[fat[u][k-1]][k-1]; for (int p=head[u];p;p=G[p].next) if (V!=fa) dfs(V,u),size[u]+=size[V]; } inline int LCA(int u,int v){ if (depth[u]<depth[v]) swap(u,v); for (int k=K-1;~k;k--) if ((depth[u]-depth[v])&(1<<k)) u=fat[u][k]; if (u==v) return u; for (int k=K-1;~k;k--) if (fat[u][k]!=fat[v][k]) u=fat[u][k],v=fat[v][k]; return fat[u][0]; } int n,m,maxd; int clr[N]; set<int> Set[N]; typedef set<int>::iterator ITER; int idx[N]; inline bool cmp(int a,int b){ return depth[a]<depth[b]; } int main(){ int Q,f; freopen("t.in","r",stdin); freopen("t.out","w",stdout); int cur,tmp; read(Q); while (Q--){ read(n); read(m); for (int i=1;i<=n;i++) read(clr[i]); for (int i=2;i<=n;i++) read(f),add(f,i,++inum); clk=0; dfs(1,0); for (int i=1;i<=n;i++) idx[i]=i; sort(idx+1,idx+n+1,cmp); maxd=depth[idx[n]]; cur=0; for (int i=1;i<=n;i++){ int x=idx[i]; Set[clr[x]].insert(pre[x]); ITER p=Set[clr[x]].find(pre[x]),_l=p,_r=p; int l=0,r=0,lca; if (p!=Set[clr[x]].begin()) l=back[*(--_l)]; if ((++_r)!=Set[clr[x]].end()) _r=p,r=back[*(++_r)]; if (l && r){ lca=LCA(l,r); Modify(tmp,cur,1,n,pre[lca],1); cur=tmp; } if (l){ lca=LCA(l,x); Modify(tmp,cur,1,n,pre[lca],-1); cur=tmp; } if (r){ lca=LCA(r,x); Modify(tmp,cur,1,n,pre[lca],-1); cur=tmp; } Modify(tmp,cur,1,n,pre[x],1); cur=tmp; if (i==n || depth[idx[i+1]]!=depth[idx[i]]) root[depth[idx[i]]]=cur; } int lastans=0,x,d; while (m--){ read(x); read(d); //x^=lastans; d^=lastans; int dep=min(maxd,depth[x]+d); lastans=Query(root[dep],1,n,pre[x],pre[x]+size[x]-1); printf("%d\n",lastans); } for (int i=1;i<=n;i++) head[i]=0; inum=0; for (int i=1;i<=n;i++) Set[i].clear(); ncnt=0; } return 0; }