长链剖分

P5903 【模板】树上 k 级祖先

学习笔记：https://www.luogu.com.cn/blog/Ynoi/zhang-lian-pou-fen-xue-xi-bi-ji
题解：
https://www.luogu.com.cn/blog/_post/204460
https://www.luogu.com.cn/blog/b6e0/tijie-P5903#
code：

#include
using namespace std;
#define MN 500005
int n,m,u,v,cnt,fa[MN],siz[MN],w[MN],top[MN],dep[MN],id[MN],ID[MN];
vectoredge[MN];
void dfs1(int x){
	siz[x]=1;
	for(int i=0;i= id[x]-id[top[x]]+1 && x!=rt){ //根结点
		k -= (id[x]-id[top[x]]+1);
		x = fa[top[x]];
	}
	return ID[id[x]-k];//如果一旦小于，则说明在重链上，线段树上就是连续的一段
}
#define ui unsigned int
ui S;
#define LL long long
inline ui get(ui x) {
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return S = x; 
}
int main(){
	n=read();m=read();scanf("%u",&S);
	rt=1;
	for(int i=1;i<=n;++i){
		fa[i]=read();
		if(!fa[i])rt=i;
		else edge[fa[i]].push_back(i);
	}
	dep[rt]=1;dfs1(rt);
	top[rt]=rt;dfs2(rt);
	LL ans=0;
	int lstans=0;
	for(int i=1;i<=m;++i){
		int x=(get(S)^lstans)%n+1;
		int k=(get(S)^lstans)%dep[x];
		lstans=jump(x,k);//返回这个k级祖先
		ans^=(LL)i*lstans;
	}
	printf("%lld\n",ans);
	return 0;
}