算法1
树上dfs(dfs序列)
时间复杂度
o(n)
C++ 代码
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 2e5+10;
vector<int> g[N],a;
//vector<int> a;
int dp[N],p[N];//dp数组是以i为根节点的子树节点数
int idx = 0;
void dfs(int point)//存的时候是从1开始遍历式的存点,所以只要直接输出就好了
{ //顺序都是一样的,做一下预处理就OK了,将所有点的遍历顺序存入vector中
p[point] = ++ idx;
a.push_back(point);
dp[point] = 1;
for(auto num : g[point])//不回溯就不需要return
{
dfs(num);//再for中所以是深搜
dp[point] += dp[num];
}
}
void pre_work()
{
a.push_back(0);
dfs(1);
}
void zxy()
{
int n,q;
cin>>n>>q;
for(int i=2;i<=n;i++)//一号节点是根节点
{
int x;cin>>x;
g[x].push_back(i);
}
//for(int i=1;i<=n;i++) sort(g[i].begin(),g[i].end());
pre_work();
while(q--)
{
int point,len;
cin>>point>>len;
if(len<=dp[point]) cout<<a[p[point] + len - 1]<<endl;
else cout<<-1<<endl;
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1; //cin>>t;
while(t--) zxy();
return 0;
}