刚学长链剖分，能过样例，但全 wa。

#include<bits/stdc++.h>
#define N 500010
#define ui unsigned int
using namespace std;
struct hhh{
	int v,next;
}dl[N];
int n,q,root,tot,cnt;
long long ans;
int lg[N],dep[N],lon[N],head[N],f[N][30],son[N],top[N],id[N],up[N],down[N];
ui s;
inline ui get(ui x){
	x^=x<<13;
	x^=x>>17;
	x^=x<<5;
	return s=x; 
}
void qxx(int u,int v){
	dl[++tot].v=v;
	dl[tot].next=head[u];
	head[u]=tot;
}
void dfs(int u,int h){
	dep[u]=lon[u]=h;
	for(int i=1;i<=20;i++){
		if(h<=(1<<i)) break;
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=dl[i].next){
		int v=dl[i].v;
		dfs(v,h+1);
		lon[u]=max(lon[u],lon[v]);
		if(lon[v]>lon[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int t){
	id[u]=++cnt;
	up[cnt]=t;
	down[cnt]=u;
	if(!son[u]) return;
	top[son[u]]=top[u],dfs2(son[u],f[t][0]);
	for(int i=head[u];i;i=dl[i].next){
		int v=dl[i].v;
		if(v!=son[u]) top[v]=v,dfs2(v,v); 
	}
}
int find(int x,int k){
	if(!k) return x;
	x=f[x][lg[k]],k-=(1<<lg[k]);
	k-=dep[x]-dep[top[x]],x=top[x];
	if(k<=0) x=down[id[x]-k];
	else x=up[id[x]+k];
}
int main(){
	cin>>n>>q>>s;
	lg[0]=-1;
	for(int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
	for(int i=1;i<=n;i++){
		cin>>f[i][0];
		if(!f[i][0]) root=i;
		else qxx(f[i][0],i);
	}
	dfs(root,1);
	top[root]=root,dfs2(root,root);
	int last=0; 
	for(int i=1;i<=q;i++){
		int x=(get(s)^last)%n+1,k=(get(s)^last)%dep[x];
		last=find(x,k);
		ans^=(long long)last*i;
	}
	cout<<ans;
	return 0;
}