rt。

代码使用 $O(n^2)$ 的暴力。

支持更改数据范围、输出每个询问及其答案。

输入文件为 P5903.in,答案文件为 P5903.ans。

代码各部分具体功能见注释。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int randint(int l,int r){
	if(r<l)swap(l,r);
	return (1ll*rand()*rand()*rand()*rand())%(r-l+1)+l;
}
int tmp[500010],fa[500010],dep[500010],root;
struct queries{
	int x,k,ans;
}query[5000010];
unsigned s;
unsigned get(unsigned x){x^=x<<13;x^=x>>17;x^=x<<5;return s=x;}
const int res=2;
vector<int> v;
void dfs(int u){
	if(dep[u])return;
	dfs(fa[u]);
	dep[u]=dep[fa[u]]+1;
}
int solve(int u,int k){//寻找u的k级祖先 
	if(k==0)return u;
	return solve(fa[u],k-1);
}
signed main(){
	srand((unsigned)time(NULL));
	int n=10,q=10000;s=randint(1ll,4294967295ll);
//开始生成输入文件
	freopen("P5903.in","w",stdout);
	cout<<n<<" "<<q<<" "<<s<<"\n";
	for(int i = 2;i<=n;i++)tmp[i]=randint(max(1ll,i-res),i-1);//生成树
	//res为一参数，可调整。res越大期望树高越低。 
	for(int i = 1;i<=n;i++)v.push_back(i);
	random_shuffle(v.begin(),v.end());//随机打乱点的顺序 
	for(int i = 1;i<=n;i++)//使用新的点序重新计算fa 
		if(tmp[i]!=0)fa[v[i-1]]=v[tmp[i]-1];
		else fa[v[i-1]]=0;
	for(int i = 1;i<=n;i++)cout<<fa[i]<<" ";
//输入文件生成完毕

//使用O(n*n)的暴力生成输出 
	freopen("P5903.ans","w",stdout); 
	for(int i = 1;i<=n;i++)if(!fa[i])root=i;
	dep[root]=1;
	for(int i = 1;i<=n;i++)if(!dep[i])dfs(i);//处理dep 
	for(int i = 1;i<=q;i++){
		query[i].x=(get(s)^query[i-1].ans)%n+1;
		query[i].k=(get(s)^query[i-1].ans)%dep[query[i].x];
		query[i].ans=solve(query[i].x,query[i].k);
	}
	//for(int i = 1;i<=q;i++)cout<<query[i].x<<" "<<query[i].k<<" "<<query[i].ans<<"\n";
	//输出每个询问及其答案，如有需要可以取消注释
	for(int i = 1;i<=q;i++)query[0].ans^=(i*query[i].ans);
	cout<<query[0].ans<<"\n";//输出最终答案 
//输出文件生成完毕 
}