题意

https://www.lydsy.com/JudgeOnline/problem.php?id=4771

思路

和 HDU 3333 其实有点像，不过是把序列的问题放在了树上，多维护一个深度即可。每个点用一个线段树维护子树内每个深度有多少种颜色（同样只保留每个颜色最浅位置），用线段树合并进行合并，由于要保留之前的颜色，所以合并应该可持久化。

为了将相同的颜色去除，再开一个线段树维护每个颜色目前的深度，若合并时出现重复情况，把深的颜色删去（也在维护深度的线段树中删去），代码比较难调。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

typedef long long LL;

using namespace std;

const int N=1e5+5;

const int NN1=N*180;

const int NN2=N*25;

template<const int maxn,const int maxm>struct Linked_list

{

	int head[maxn],to[maxm],nxt[maxm],tot;

	Linked_list(){clear();}

	void clear(){memset(head,-1,sizeof(head));tot=0;}

	void add(int u,int v){to[++tot]=v,nxt[tot]=head[u],head[u]=tot;}

	#define EOR(i,G,u) for(int i=G.head[u];~i;i=G.nxt[i])

};

Linked_list<N,N>G;

int dep[N],col[N],n,m;

struct SegmentTree1

{

	int sum[NN1],lson[NN1],rson[NN1];

	int rt[N],tot;

	int &operator [](const int &x){return rt[x];}

	void build()

	{

		memset(rt,0,sizeof(rt));

		sum[tot=0]=lson[0]=rson[0]=0;

	}

	void Create(int &k)

	{

		sum[++tot]=sum[k],lson[tot]=lson[k],rson[tot]=rson[k],k=tot;

	}

	void update(int &k,int x,int val,int l,int r)

	{

		Create(k);

		sum[k]+=val;

		if(l==r)return;

		int mid=(l+r)>>1;

		if(x<=mid)update(lson[k],x,val,l,mid);

		else update(rson[k],x,val,mid+1,r);

	}

	int query(int k,int L,int R,int l,int r)

	{

		if(L<=l&&r<=R)return sum[k];

		int mid=(l+r)>>1;

		if(R<=mid)return query(lson[k],L,R,l,mid);

		else if(L>mid)return query(rson[k],L,R,mid+1,r);

		else return query(lson[k],L,R,l,mid)+query(rson[k],L,R,mid+1,r);

	}

	void merge(int &x,int y,int l,int r)

	{

		if(!x||!y){x=(x|y);return;}

		Create(x);

		if(l==r){sum[x]+=sum[y];return;}

		int mid=(l+r)>>1;

		merge(lson[x],lson[y],l,mid);

		merge(rson[x],rson[y],mid+1,r);

		sum[x]=sum[lson[x]]+sum[rson[x]];

	}

}ST1;

//ST1[i] 以i为根的子树，每个深度有多少个节点（不同色）

struct SegmentTree2

{

	int lson[NN2],rson[NN2];

	int Mi[NN2],rt[N],tot;

	int &operator [](const int &x){return rt[x];}

	void build()

	{

		memset(rt,0,sizeof(rt));

		Mi[tot=0]=1e9;

		lson[0]=rson[0]=0;

	}

	void create(int &k)

	{

		if(!k)k=++tot,Mi[k]=1e9,lson[k]=rson[k]=0;

	}

	void update(int &k,int x,int val,int l,int r)

	{

		create(k);

		if(l==r){Mi[k]=min(Mi[k],val);return;}

		int mid=(l+r)>>1;

		if(x<=mid)update(lson[k],x,val,l,mid);

		else update(rson[k],x,val,mid+1,r);

	}

	int query(int k,int x,int l,int r)

	{

		if(l==r)return Mi[k];

		int mid=(l+r)>>1;

		if(x<=mid)return query(lson[k],x,l,mid);

		else return query(rson[k],x,mid+1,r);

	}

	void merge(int &x,int y,int &id,int l,int r)

	{

		if(!x||!y){x=(x|y);return;}

		if(l==r)

		{

			ST1.update(id,max(Mi[x],Mi[y]),-1,1,n);

			Mi[x]=min(Mi[x],Mi[y]);

			return;

		}

		int mid=(l+r)>>1;

		merge(lson[x],lson[y],id,l,mid);

		merge(rson[x],rson[y],id,mid+1,r);

	}

}ST2;

//ST2[i] 以i为根的子树，每种颜色出现的最浅深度

int main()

{

	int T;

	scanf("%d",&T);

	while(T--)

	{

		G.clear();

		scanf("%d%d",&n,&m);

		FOR(i,1,n)scanf("%d",&col[i]);

		dep[1]=1;

		FOR(v,2,n)

		{

			int u;

			scanf("%d",&u);

			G.add(u,v);

			dep[v]=dep[u]+1;

		}

		ST1.build(),ST2.build();

		DOR(u,n,1)

		{

			ST1.update(ST1[u],dep[u],1,1,n);

			ST2.update(ST2[u],col[u],dep[u],1,n);

			EOR(i,G,u)

			{

				int v=G.to[i];

				ST1.merge(ST1[u],ST1[v],1,n);

				ST2.merge(ST2[u],ST2[v],ST1[u],1,n);

			}

		}

		int x,d,lst=0;

		while(m--)

		{

			scanf("%d%d",&x,&d);

			x^=lst,d^=lst;

			printf("%d\n",lst=ST1.query(ST1[x],dep[x],min(n,dep[x]+d),1,n));

		}

	}

    return 0;

}