此题 $n=5e5,q=5e6$ ，按LCT的复杂度计算，$5e6*log(5e5)$，理论上时间复杂度正确，应当能满足3S的时限。但求助为什么还是有三个点TLE了...常数在大也不应该慢成这样啊... 代码：

#include <bits/stdc++.h>
using namespace std;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}
	return x*f;
}

const int N=5e5+7;

int n,q;
long long ans;

struct S{
	S *ls,*rs,*fa;int val,size,rev;
	inline bool get(){return fa->ls==this;}
	inline bool isrt(){return fa->ls!=this&&fa->rs!=this;}
	inline void pushUp(){size=ls->size+rs->size+1;}
	inline void reverse(){swap(ls,rs);rev^=1;}
	inline void pushDown(){if(!rev)return;ls->reverse();rs->reverse();rev=0;}
}tree[N],*null=tree;
inline void rotate(S *x){
	bool f=!x->get();S *SN=f?x->ls:x->rs,*FA=x->fa,*GF=FA->fa;
	if(!FA->isrt()) FA->get()?GF->ls=x:GF->rs=x;x->fa=GF;
	SN->fa=FA;f?FA->rs=SN:FA->ls=SN;FA->fa=x;f?x->ls=FA:x->rs=FA;
	FA->pushUp();x->pushUp();
}
void pushAll(S *x){if(!x->isrt())pushAll(x->fa);x->pushDown();}
void splay(S *x){
	for(pushAll(x);!x->isrt();rotate(x))
		if(!x->fa->isrt()) rotate(x->fa->get()==x->get()?x->fa:x);
}
inline void maketree(S *x,int num){x->fa=x->ls=x->rs=null;x->size=1;x->val=num;}
inline void access(S *x){
	for(S *last=null;x!=null;last=x,x=x->fa)
		splay(x),x->rs=last,x->pushUp();
}
inline void makert(S *x){
	access(x);splay(x);
	x->reverse();
}
inline S *findrt(S *x){
	access(x);splay(x);
	while(x->ls!=null) x->pushDown(),x=x->ls;splay(x);
	return x;
}
void link(S *x,S *y){
	makert(x);
	if(findrt(y)!=x) x->fa=y;
}
void cut(S *x,S *y){
	makert(x);
	if(findrt(y)==x&&y->fa==x&&y->ls==null)
		x->rs=y->fa=null,x->pushUp();
}

S *getKth(S *x,int k){
	while(1){
//		cout<<k<<' '<<x->val<<' '<<x->ls->size<<endl;
		if(k>x->ls->size+1) k-=x->ls->size+1,x=x->rs;
		if(k==x->ls->size+1) return x;
		if(k<x->ls->size+1) x=x->ls;
	}
	exit(0);
}
int query(int X,int k){
	S *x=&tree[X];
	access(x);splay(x);
	return getKth(x,x->size-k)->val;
}

#define ui unsigned int
ui s;

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

#undef ui

struct T{int v,next;}edge[N<<1];
int f[N],cnt;
void insert(int u,int v){
	edge[++cnt]=T{v,f[u]};f[u]=cnt;
	edge[++cnt]=T{u,f[v]};f[v]=cnt;
}

int deep[N];
void dfs(int u,int fa){
	deep[u]=deep[fa]+1;
	for(int i=f[u];i;i=edge[i].next){
		int v=edge[i].v;
		if(v^fa) dfs(v,u);
	}
}

int main(){
//	freopen("in","r",stdin);
	n=read(),q=read(),s=read();
	for(int i=1;i<=n;i++) maketree(&tree[i],i);
	int x,root;
	for(int i=1;i<=n;i++){
		x=read();
		if(x) link(&tree[i],&tree[x]),insert(x,i);
		else root=i;
	}
	makert(&tree[root]);
	dfs(root,0);
	int lastans=0,k;
	for(int i=1;i<=q;i++){
		x=(get(s)^lastans)%n+1;
		k=(get(s)^lastans)%deep[x];
		ans^=1ll*i*(lastans=query(x,k));
	}
	printf("%lld\n",ans);
	return 0;
}```