长链剖分

基本定义

长剖跟树剖很像，都是链剖分形式。区别在于，重儿子在树剖中定义为子树大小最大的儿子，而长剖中定义为子树深度最大的儿子。顺理成章地，不是重儿子的就是轻儿子，指向重儿子的边为重边，其余为轻边。重边所构成的链成为重链（为区别树剖与长剖，下文使用长链），特殊地，单节点也可作为一条重链。

接下来说说长剖的性质。

  • 性质一：树上所有长链长度和 $O(n)$

比较好理解，因为一个点只能存在于一条长链。

  • 性质二：任意节点通过长链跳到根，最多跳 $O(\sqrt n)$ 次

因为每次跳到的长链都会比原来的长链长（否则长链就是这个了），所以最坏情况长链长度从 $1$ 到 $\sqrt n$，总共跳 $O(\sqrt n)$ 次。

树上 k 级祖先

法 $1$：倍增预处理，复杂度 $O(n\log n)-O(\log n)$。

法 $2$：树剖，跳重链，复杂度 $O(n)-O(\log n)$，加二分可以做到 $O(n\log n)-O(\log\log n)$。

但还不够优秀！长剖做法可以做到 $O(n\log n)-O(1)$。

具体地，我们先倍增预处理 $2^k$ 祖先，还有每个长链顶点向上向下长链长度（记为 $d$）的数组。也就是 $v_{i,j}$ 表示 $i$ 点（是一条长链的顶点）向上/向下 $j$ 个的点。

对于 $k$，找到最大的 $i$，使得 $2^i\le k<2^{i+1}$。此时从 $x$ 跳到其 $2^i$ 的父亲 $y$，还需要跳 $k-2^i$ 级。我们记 $y$ 所在长链长度为 $d$，那么 $k-2^i<2^i\le d$。

因为任意点的 $k$ 级祖先所在长链长度大于等于 $k$， 这一点容易发现，反证得若不满足，则祖先到儿子这条链更优。

于是我们跳到 $y$ 的链顶，用预处理的数组求剩下的部分。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=5e5+10;
int n,q,rt;
ll res,ans;
#define ui unsigned int
ui s;
ui get(ui x){
    x^=x<<13;
    x^=x>>17;
    x^=x<<5;
    return s=x; 
}
vector<int> e[N],v1[N],v2[N];
int son[N],fa[N][21],len[N],top[N],mx[N],d[N],lg[N];
void dfs(int u,int f){
    d[u]=d[f]+1,mx[u]=d[u];
    for(int i=0;i<=19;++i) fa[u][i+1]=fa[fa[u][i]][i];
    for(int v:e[u]){
        if(v==f) continue;
        fa[v][0]=u,dfs(v,u);
        if(mx[v]>mx[son[u]]) son[u]=v,mx[u]=mx[v];
    }
}
void dfs2(int u,int t){
    top[u]=t,len[u]=mx[u]-d[top[u]]+1;
    if(son[u]) dfs2(son[u],t);
    for(int v:e[u]) if(v!=fa[u][0]&&v!=son[u]) dfs2(v,v);
}
int query(int x,int k){
    if(k==0) return x;
    int t=lg[k];
    k-=(1<<t),x=fa[x][t];
    k-=d[x]-d[top[x]],x=top[x];
    if(k==0) return x;
    return k>0?(v1[x][k-1]):(v2[x][-k-1]);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q>>s;
    lg[0]=-1;
    for(int i=1,x,y;i<=n;++i){
        cin>>x;
        lg[i]=lg[i>>1]+1;
        if(x==0) rt=i;
        else e[x].push_back(i);
    }
    dfs(rt,0),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,y=i;j<=len[i];++j){
            y=son[y];
            v2[i].push_back(y);
        }
    }
    for(int i=1,x=0,k=0;i<=q;++i){
        x=(get(s)^res)%n+1,k=(get(s)^res)%d[x];
        res=query(x,k);
        ans^=i*res;
    }
    cout<<ans<<endl;
    return 0;
}