长链剖分基本定义长剖跟树剖很像，都是链剖分形式。区别在于，重儿子在树剖中定义为子树大小最大的儿子，而长剖中定义为子树深度最大的儿子。顺理成章地，不是重儿子的就是轻儿子，指向重儿子的边为重边，其余为轻边。重边所构成的链成为重链（为区别树剖与长剖，下文使用长链），特殊地，单节点也可作为一条重链。
接下来说说长剖的性质。
性质一：树上所有长链长度和 $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$ 的链顶，用预处理的数组求剩下的部分。
#includeusing namespace std;#define ll long long#define endl '\n'const int N=5e5+10;int n,q,rt;ll res,ans;#define ui unsigned intui s;ui get(ui x){ x^=x<<13; x^=x>>17; x^=x<<5; return s=x; }vector 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<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<
