https://oi-wiki.org/graph/hld
https://www.cnblogs.com/maoyiting/p/14178833.html#/cnblog/works/article/14178833

定义 重子节点 表示其子节点中子树深度最大的子结点。

长链剖分实现方式和重链剖分类似。
第一次dfs处理出以下四个数组
$dep$表示节点深度
$fa$表示节点父亲
$son$表示重子节点编号
$mx$表示该节点最深能到达的深度。
第二次dfs处理一下数组
$top$表示所在长链的顶点
$len$表示所在长链的长度
$dfn、rnk$数组

dep[rt] = 1;
void dfs1(int u){
    son[u] = -1;
    mx[u] = dep[u];
    for(int i=0;i<=25;i++) fa[u][i+1] = fa[fa[u][i]][i];
    for(auto v:g[u]){
        if(!dep[v]){
            dep[v] = dep[u] + 1;
            fa[v][0] = u;
            dfs1(v);
            if(son[u]==-1||mx[v] > mx[son[u]]) mx[u] = mx[v],son[u] = v;
            //要先判son[u]==-1,不然有的编译器会出问题
        }
    }
}
void dfs2(int u,int t){
    top[u] = t;
    len[u] = mx[u] - dep[t] + 1;
    if(son[u]!=-1) dfs2(son[u],t);
    for(auto v:g[u]){
        if(v==fa[u][0]||v==son[u]) continue;
        dfs2(v,v);
    }
}

长链剖分的性质

• 性质一：对树长链剖分后，树上所有长链的长度和为 O(n)。
• 性质二：任意一个节点 x的k级祖先y所在长链的长度一定大于等于k。
  证明：如果存在y所在的长链长度小于k，则那么y->x这条链比长链更长，与定义矛盾。
• 性质三：任意一个节点x通过长链跳到根节点，跳跃的次数最多为 $O(\sqrt{n})$。
  ·证明：如果一个节点 x从一条长链跳到了另外一条长链上，那么跳跃到的这条长链的长度不会小于之前的长链长度。最坏情况下，链长分别为$ 1,2,⋯,\sqrt{n}$也就是最多跳跃 $\sqrt{n}$次。

长链剖分求k级祖先

1.倍增预处理x的$2^i$级祖先
2.跑长链剖分
3.对每个长链顶点x，设所在长链长度为d，处理x向上的d个节点和向下的d个节点。
4.对一个询问，求x的k祖先。设$$2^i\leqslant k \leqslant 2^{i+1}$$ 则先把x往上跳$2^i$次，这个时候还要往上跳$k_1 = k-2^i次$，由性质2，x所在长链长度$d \geqslant k_1$，所以此时再跳到长链顶部，x的k祖先要么最多在这条长链往下d个，要么最多在长链顶往上d个。根据长链顶预处理的数组直接查询即可。
https://www.luogu.com.cn/problem/P5903

#include<bits/stdc++.h>
#define LOCAL//delete when submit!!!!!!


using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const int N  = 5e5+10;
int dep[N],son[N],mx[N],fa[N][30],top[N];
int len[N];//表示节点u所在长链的长度
vector<vector<int>> g;
vector<int> v1[N],v2[N];//长链顶点向上向下的d个节点
int n,q;
int rt;
unsigned s;
unsigned int get(unsigned int x){
    x^=x<<13,x^=x>>17,x^=x<<5;
    return s=x;
}
void dfs1(int u){
    son[u] = -1;
    mx[u] = dep[u];
    for(int i=0;i<=25;i++) fa[u][i+1] = fa[fa[u][i]][i];
    for(auto v:g[u]){
        if(!dep[v]){
            dep[v] = dep[u] + 1;
            fa[v][0] = u;
            dfs1(v);
            if(mx[v] > mx[son[u]]|| son[u]==-1) mx[u] = mx[v],son[u] = v;            
        }
    }
}
void dfs2(int u,int t){
    top[u] = t;
    len[u] = mx[u] - dep[t] + 1;
    if(son[u]!=-1) dfs2(son[u],t);
    for(auto v:g[u]){
        if(v==fa[u][0]||v==son[u]) continue;
        dfs2(v,v);
    }
}

int query(int x,int k){
    if(!k) return x;
    int t = log(k)/log(2);
    x = fa[x][t];
    k-=(1<<t);
    k -= dep[x] - dep[top[x]]; 
    x = top[x];
    if(!k) return x;
    return k>0?v1[x][k-1]:v2[x][-k-1];//下标0是往上或往下的第一个节点，所以要减一
}

void solve(){
    cin>>n>>q>>s;
    g = vector<vector<int>>(n+1);
    for(int i=1;i<=n;i++){
        int x; cin>>x;
        if(!x) rt = i;
        else{
            g[x].push_back(i);
            g[i].push_back(x);
        }
    }
    dep[rt] = 1;
    dfs1(rt);
    dfs2(rt,rt);
    for(int i=1;i<=n;i++){
        if(i!=top[i]) continue;
        for(int j=1,x=i;j<=len[i];j++){
            x = fa[x][0],v1[i].push_back(x);
        }
        for(int j=1,x=i;j<=len[i];j++){
            x = son[x],v2[i].push_back(x);
        }
    }
    ll res = 0;
    ll ans = 0; 
    for(ll i=1;i<=q;i++){
        ll x=(get(s)^res)%n+1, k = (get(s)^res)%dep[x];
        res = query(x,k);
        ans ^= i*res;
    }
    cout<<ans<<endl;
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}