非长链剖分解法！！！

k级祖先问题，依然考虑树链剖分。

我们首先进行重链剖分，求x的k级祖先，就从x开始往上跳，然后就解决了。最后跑的比绝大多长链剖分做法都快。(洛谷最优解第二页)...

#include<bits/stdc++.h>
using namespace std;
#define ui unsigned int
#define ll long long
const int N=5e5+10;int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();return x*f;
}ui s;
int n,q,rt,head[N],tot;
int fa[N],dep[N],sz[N],son[N],top[N],dfn[N],idx,DFN[N];
struct node{int to,nxt;
}edge[N*2];
void add(int x,int y){edge[++tot].to=y;edge[tot].nxt=head[x];head[x]=tot;
}void dfs1(int x,int father){sz[x]=1,dep[x]=dep[father]+1;for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(y==father) continue;dfs1(y,x);sz[x]+=sz[y];if(sz[son[x]]<sz[y]) son[x]=y;}
}void dfs2(int x,int t){top[x]=t,dfn[x]=++idx,DFN[idx]=x;if(!son[x]) return;dfs2(son[x],t);for(int i=head[x];i;i=edge[i].nxt){int y=edge[i].to;if(y==fa[x]||y==son[x]) continue;dfs2(y,y);}
}int k_ancestor(int x,int k){while(k>=dfn[x]-dfn[top[x]]+1&&x!=rt){k-=dfn[x]-dfn[top[x]]+1;x=fa[top[x]];}return DFN[dfn[x]-k];
}ui get(ui x){x^=x<<13,x^=x>>17,x^=x<<5;return s=x;
}int main(){n=read(),q=read(),cin>>s;int T=0;for(int i=1;i<=n;i++){fa[i]=read();if(!fa[i]) rt=i;else add(fa[i],i),add(i,fa[i]);}dfs1(rt,0),dfs2(rt,rt);int la=0;ll ans=0;while(q--){T++;int x=((get(s)^la)%n)+1,k=(get(s)^la)%dep[x];la=k_ancestor(x,k),ans^=(ll)T*la;}cout<<ans<<endl;return 0;
}