P5903 【模板】树上 k 级祖先

模板题，但因为用到不少小trick，特此记录

题解：

出题人题解讲的很好，我就不说了：这里

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define ui unsigned int

const int N=5e5+5;
int en,h[N],n,q,S,d[N],dep[N],s[N],f[N][21],top[N],lim[N],rt,ans;
vector<int> up[N],down[N];
long long xum;

struct edge{
    int n,v;
}e[N];

void add(int x,int y){
    e[++en]=(edge){h[x],y};
    h[x]=en;
}

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

void dfs1(int x){
    dep[x]=d[x]=d[f[x][0]]+1;
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        for(int j=0;f[y][j];j++)
            f[y][j+1]=f[f[y][j]][j];
        dfs1(y);
        if(dep[y]>dep[x]) dep[x]=dep[y],s[x]=y; 
    }
}

void dfs2(int x,int TOP){
    top[x]=TOP;
    if(x==TOP){
        for(int i=0,pt=x;i<=dep[x]-d[x];i++)
            up[x].push_back(pt),pt=f[pt][0];
        for(int i=0,pt=x;i<=dep[x]-d[x];i++)
            down[x].push_back(pt),pt=s[pt];
    }
    if(s[x]) dfs2(s[x],TOP);
    for(int i=h[x];i;i=e[i].n){
        int y=e[i].v;
        if(y^s[x]) dfs2(y,y);
    }
}

int que(int x,int k){
    if(!k) return x;
    x=f[x][lim[k]];
    k-=1<<lim[k];
    k-=d[x]-d[top[x]];
    x=top[x];
    if(k>=0) return up[x][k];
    return down[x][-k];
}

signed main(){
    read(n);read(q);read(S);
    for(int i=1,x;i<=n;i++){
        read(x);
        if(x) add(x,i),f[i][0]=x;
        else rt=i;
    }
    lim[0]=-1;
    for(int i=1;i<=n;i++) lim[i]=lim[i>>1]+1;
    dfs1(rt);
    dfs2(rt,rt);
    for(int i=1,x,k;i<=q;i++){
        x=(get(S)^ans)%n+1,k=(get(S)^ans)%d[x];
        xum^=1ll*i*(ans=que(x,k));
    }
    write(xum);
}