给定一棵 n 个点的有根树。

有 q 次询问，第 i 次询问给定 xi, ki，要求点 xi 的 ki 级祖先。

保证ki合法。

一、树链剖分——重链剖分 O（n+qlogn）：
7.46s

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;

#define ui unsigned int
ui s;
inline ui get(ui x)
{
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x;
}


const int maxn=500100;
int head[maxn],ver[maxn],nt[maxn];
int f[maxn],d[maxn],si[maxn],son[maxn],rk[maxn];
int top[maxn],id[maxn],vi[maxn];
int tot=1,cnt=0,n,q,rt;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x)
{
    int max_son=0;
    si[x]=1;
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        d[y]=d[x]+1;

        dfs1(y);

        si[x]+=si[y];
        if(si[y]>max_son)max_son=si[y],son[x]=y;
    }
}

void dfs2(int x,int t)
{
    top[x]=t;
    id[x]=++cnt;
    rk[cnt]=x;

    if(!son[x]) return ;
    dfs2(son[x],t);

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y!=son[x])
            dfs2(y,y);
    }
}

int fi(int x,int k)
{
    while(x!=rt&&k>=id[x]-id[top[x]]+1)
    {
        k-=id[x]-id[top[x]]+1;
        x=f[top[x]];
    }
    return rk[id[x]-k];
}

int main(void)
{
    int x,k;
    scanf("%d%d%u",&n,&q,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
        if(f[i]) add(f[i],i);
        else rt=i;
    }
    d[rt]=1;
    dfs1(rt);
    dfs2(rt,rt);

    ui ans=0;
    ll res=0;
    for(int i=1;i<=q;i++)
    {
        x=((get(s)^ans)%n)+1;
        k=(get(s)^ans)%d[x];
        ans=fi(x,k);
        res=res^((ll)i*ans);
    }
    printf("%lld\n",res);
    return 0;
}

二、树链剖分——长链剖分 O（nlogn + q）：
12.31s
大概是我姿势不太对。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;

#define ui unsigned int
ui s;
inline ui get(ui x)
{
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x;
}


const int maxn=500100;
int head[maxn],ver[maxn],nt[maxn];
int f[maxn][22],d[maxn],h[maxn],son[maxn];
int top[maxn],id[maxn],lo[maxn],up[maxn],down[maxn];
int tot=1,cnt=0,n,q,rt,t;

void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}

void dfs1(int x)
{

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        d[y]=h[y]=d[x]+1;
        for(int j=1;j<=t;j++)
            f[y][j]=f[f[y][j-1]][j-1];

        dfs1(y);

        if(h[y]>h[x]) h[x]=h[y],son[x]=y;
    }
}

void dfs2(int x,int t,int p)
{
    id[x]=++cnt;
    top[x]=t;
    up[cnt]=p;
    down[cnt]=x;

    if(!son[x]) return ;

    dfs2(son[x],t,f[p][0]);

    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        if(y!=son[x])
            dfs2(y,y,y);
    }
}

int fi(int x,int k)
{
    if(!k) return x;
    x=f[x][lo[k]];
    k-=(1<<lo[k]);
    k-=id[x]-id[top[x]];
    x=top[x];
    if(k>=0) return up[id[x]+k];
    else return down[id[x]-k];
}

int main(void)
{
    int x,k;
    scanf("%d%d%u",&n,&q,&s);

    lo[0]=-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i][0]);
        if(f[i][0]) add(f[i][0],i);
        else rt=i;
        lo[i]=lo[i>>1]+1;
    }

    d[rt]=h[rt]=1,t=log2(n)+1;
    dfs1(rt);
    dfs2(rt,rt,rt);

    ui ans=0;
    ll res=0;
    for(int i=1;i<=q;i++)
    {
        x=((get(s)^ans)%n)+1;
        k=(get(s)^ans)%d[x];
        ans=fi(x,k);
        res=res^((ll)i*ans);
    }
    printf("%lld\n",res);
    return 0;

}