好题，又学两个思路。
先把问题变简单一点，去掉深度限制，那么有两种做法：
-
经典的前驱后继转化到二维数点。
-
颜色相同的点按 \(dfs\) 序排序，每个点 \(+1\)，相邻两点 \(lca-1\)。转化为区间求和。
第二种相对实现简单。
假如加上深度，我们可以离线问题，按深度顺序加点。
要在线的话，只需要将线段树改为主席树即可。
时间复杂度 \(O(\sum (n+m)\log n)\)。
除了刚才说到的主席树外，本题在实现过程中还需要用到单调栈（记录自己插入时已经插入且颜色相同的前驱后继）。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=3e7+5;
int n,tot,low[N],id;
int m,q,dfn[N],a[N];
int tp,sk[N],ij,rt[N];
int t,dep[N],st[N][20];
int fs[N],pr[N],nx[N];
int ls[M],rs[M],sm[M];
vector<int>g[N],cl[N];
int cmp(int x,int y){
return dfn[x]<dfn[y];
}int cmd(int x,int y){
return dep[x]<dep[y];
}int cmb(int x,int y){
return dep[x]!=dep[y]?cmd(x,y):x<y;
}void dfs(int x,int fa){
fs[x]=++ij,dfn[x]=++id;
dep[st[ij][0]=x]=dep[fa]+1;
for(auto y:g[x])
dfs(y,x),st[++ij][0]=x;
low[x]=id;
}int minn(int x,int y){
return dep[x]>dep[y]?y:x;
}void ST(){
for(int i=0;i<19;i++)
for(int j=1;j<=ij-(1<<(i+1))+1;j++)
st[j][i+1]=minn(st[j][i],st[j+(1<<i)][i]);
}int rmq(int l,int r){
int k=log2(r-l+1),x=r-(1<<k)+1;
return minn(st[l][k],st[x][k]);
}int lca(int x,int y){
if(fs[x]>fs[y]) swap(x,y);
return rmq(fs[x],fs[y]);
}void add(int &x,int y,int l,int r,int k,int v){
sm[x=++tot]=sm[y]+v;
if(l==r) return;int mid=(l+r)/2;
if(k<=mid) add(ls[x],ls[y],l,mid,k,v),rs[x]=rs[y];
else add(rs[x],rs[y],mid+1,r,k,v),ls[x]=ls[y];
}int sum(int x,int y,int l,int r,int L,int R){
if(L>R) return 0;
if(L<=l&&r<=R) return sm[x]-sm[y];
int mid=(l+r)/2,re=0;
if(L<=mid) re=sum(ls[x],ls[y],l,mid,L,R);
if(R>mid) re+=sum(rs[x],rs[y],mid+1,r,L,R);
return re;
}void solve(){
for(int i=1;i<=n;i++)
pr[i]=nx[i]=0,g[i].clear(),cl[i].clear();
cin>>n>>q,tot=id=ij=0;int la=0;
for(int i=1,x;i<=n;i++)
cin>>x,a[i]=i,cl[x].push_back(i);
for(int i=2,x;i<=n;i++)
cin>>x,g[x].push_back(i);
dfs(1,0),ST();
sort(a+1,a+n+1,cmd),m=dep[a[n]];
for(int i=1,k;i<=n;i++){
k=cl[i].size(),sort(cl[i].begin(),cl[i].end(),cmp);
for(int j=0;j<k;j++){
while(tp&&cmb(cl[i][j],cl[i][sk[tp]])) tp--;
if(tp) pr[cl[i][j]]=cl[i][sk[tp]];sk[++tp]=j;
}while(tp) sk[tp--]=0;
for(int j=k-1;~j;j--){
while(tp&&cmb(cl[i][j],cl[i][sk[tp]])) tp--;
if(tp) nx[cl[i][j]]=cl[i][sk[tp]];sk[++tp]=j;
}while(tp) sk[tp--]=0;
}for(int i=1;i<=n;i++){
int nw=dep[a[i]];rt[nw]=rt[dep[a[i-1]]];
add(rt[nw],rt[nw],1,n,dfn[a[i]],1);
if(nx[a[i]]) add(rt[nw],rt[nw],1,n,dfn[lca(a[i],nx[a[i]])],-1);
if(pr[a[i]]) add(rt[nw],rt[nw],1,n,dfn[lca(a[i],pr[a[i]])],-1);
if(nx[a[i]]&&pr[a[i]])
add(rt[nw],rt[nw],1,n,dfn[lca(pr[a[i]],nx[a[i]])],1);
}while(q--){
int x,d;cin>>x>>d,x^=la,d^=la;
la=sum(rt[min(dep[x]+d,m)],rt[dep[x]-1],1,n,dfn[x],low[x]);
cout<<la<<"\n";
}
}int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>t;
while(t--) solve();
return 0;
}