rt，时间复杂度是 $\mathcal O(n \log n)$ 的。

#include<bits/stdc++.h>
#define il inline
#define rg register
using namespace std;
const int N=1e6+5,M=2e7+5;
int n,m,a[N],f[N],dep[N],st[N],ed[N],tot,s[N],cnt,rt[N],sum[M],ls[M],rs[M];
vector<int>edge[N];
il int read(){ 
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){
		if(s=='-') f=-1;
		s=getchar();
	}
	while(s>='0'&&s<='9'){
		x=x*10+s-'0';
		s=getchar();
	}
	return x*f;
}
il void dfs(int u){
	st[u]=++tot;
	s[u]=a[u];
	for(int v:edge[u]){
		dep[v]=dep[u]+1;
		dfs(v);
		s[u]^=s[v];
	}
	ed[u]=tot;
}
il void modify(int &x,int l,int r,int h,int v){
	if(!x) x=++cnt;
	if(l==r){
		sum[x]=v;
		return;
	}
	int mid=(l+r)/2;
	if(h<=mid) modify(ls[x],l,mid,h,v);
	else modify(rs[x],mid+1,r,h,v);
	sum[x]=sum[ls[x]]^sum[rs[x]];
}
il int query(int x,int l,int r,int L,int R){
	if(!x) return 0;
	if(l>=L&&r<=R) return sum[x];
	int mid=(l+r)/2,ret=0;
	if(L<=mid) ret^=query(ls[x],l,mid,L,R);
	if(R>mid) ret^=query(rs[x],mid+1,r,L,R);
	return ret;
}
int main(){
	n=read(),m=read();
	for(rg int i=1;i<=n;i++) a[i]=read();
	for(rg int i=1;i<n;i++){
		f[i]=read();
		edge[f[i]].push_back(i+1);
	}
	dfs(1);
	for(rg int i=1;i<=n;i++) modify(rt[dep[i]],1,n,st[i],s[i]);
	for(rg int x,h;m;m--){
		x=read(),h=read();
		printf("%.3f\n",double(s[x]^query(rt[dep[x]+h+1],1,n,st[x],ed[x]))/1000*1.0);
	}
	return 0;
}