RT，不知道哪里有问题

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
template <typename T>
inline void read(T& r) {
    r=0;bool w=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=(r<<3)+(r<<1)+(ch^48), ch=getchar();
    r=w?-r:r;
}

#define ui unsigned int
ui s;

ui get(ui x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x; 
}

const int N=5e5+10;

int n,q,rt;
int h[N],e[N],ne[N],idx,lg[N];
int fa[N][25],son[N],dep[N],d[N],top[N];
vector<int> up[N],down[N];

void add(int a,int b){
    e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}

void dfs1(int u){
    d[u]=d[fa[u][0]]+1;
    for(int i=1;i<=19;++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];
        dfs1(v);
        if(dep[v]>dep[son[u]])son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int t){
    top[u]=t;
    if(u==t){
        for(int i=0,p1=u,p2=u;i<=dep[u]-d[u];++i){
            up[u].push_back(p1);
            down[u].push_back(p2);
            p1=fa[p1][0],p2=son[p2];
        }
    }
    if(son[u])dfs2(son[u],t);
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];if(v==son[u])continue;
        dfs2(v,v);
    }
    
}
int query(int u,int k){
    if(!k)return u;
    u=fa[u][lg[k]],k-=1<<lg[k];
    k-=d[u]-d[top[u]],u=top[u];
    return k>0?up[u][k]:down[u][-k];
}

int main(){
    read(n),read(q),read(s);
    for(int i=1,f;i<=n;++i){
        read(f);fa[i][0]=f;
        if(!f)rt=i; else add(f,i);
        if(i>1)lg[i]=lg[i>>1]+1;
    }
    dfs1(rt),dfs2(rt,rt);
    int x,k,lstans=0;long long ans=0;
    for(int i=1;i<=q;++i){
        x=((get(s)^lstans)%n)+1;
        k=(get(s)^lstans)%d[x];
        lstans=query(x,k);
        ans^=1ll*i*lstans;
        
    }
    printf("%lld\n",ans);
    return 0;
}#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
template <typename T>
inline void read(T& r) {
    r=0;bool w=0; 
    char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=(r<<3)+(r<<1)+(ch^48), ch=getchar();
    r=w?-r:r;
}

#define ui unsigned int
ui s;

ui get(ui x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x; 
}

const int N=5e5+10;

int n,q,rt;
int h[N],e[N],ne[N],idx,lg[N];
int fa[N][25],son[N],dep[N],d[N],top[N];
vector<int> up[N],down[N];

void add(int a,int b){
    e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}

void dfs1(int u){
    d[u]=d[fa[u][0]]+1;
    for(int i=1;i<=19;++i)
        fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];
        dfs1(v);
        if(dep[v]>dep[son[u]])son[u]=v;
    }
    dep[u]=dep[son[u]]+1;
}
void dfs2(int u,int t){
    top[u]=t;
    if(u==t){
        for(int i=0,p1=u,p2=u;i<=dep[u]-d[u];++i){
            up[u].push_back(p1);
            down[u].push_back(p2);
            p1=fa[p1][0],p2=son[p2];
        }
    }
    if(son[u])dfs2(son[u],t);
    for(int i=h[u];i;i=ne[i]){
        int v=e[i];if(v==son[u])continue;
        dfs2(v,v);
    }
    
}
int query(int u,int k){
    if(!k)return u;
    u=fa[u][lg[k]],k-=1<<lg[k];
    k-=d[u]-d[top[u]],u=top[u];
    return k>0?up[u][k]:down[u][-k];
}

int main(){
    read(n),read(q),read(s);
    for(int i=1,f;i<=n;++i){
        read(f);fa[i][0]=f;
        if(!f)rt=i; else add(f,i);
        if(i>1)lg[i]=lg[i>>1]+1;
    }
    dfs1(rt),dfs2(rt,rt);
    int x,k,lstans=0;long long ans=0;
    for(int i=1;i<=q;++i){
        x=((get(s)^lstans)%n)+1;
        k=(get(s)^lstans)%d[x];
        lstans=query(x,k);
        ans^=1ll*i*lstans;
        
    }
    printf("%lld\n",ans);
    return 0;
}