dfs序列
作者:
摩西摩西_8
,
2022-11-30 11:32:44
,
所有人可见
,
阅读 176
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e5+10;
int n, m;
int q[N], p[N];
//q[i]表示第i个在dfs序中的数
//p[i]表示第i个数在dfs序中的下标
vector<int> g[N];//存储图
int top, se[N];
//top表示当前用到了第几个点,se[i]存储以i为根节点的子树中点的个数
void dfs(int u)
{
se[u]=1;//以u为根节点的子树中点的个数起码是1个
q[top]=u, p[u]=top++;
for (auto& v:g[u])
{
dfs(v);
se[u]+=se[v];
}
}
int main()
{
cin>>n>>m;
for (int i=2;i<=n;i++)
{
int x;
cin>>x;
g[x].push_back(i);//每一个父节点插入子节点
//x表示第i个点的父节点
}
for (int i=1;i<=n;i++) sort(g[i].begin(), g[i].end());//每一棵子树排序
dfs(1);
while(m--)
{
int u, k;
cin>>u>>k;
if(k>se[u]) puts("-1");//当k大于当前子树中点的个数时
else printf("%d\n", q[p[u]+k-1]);//p[u]表示u在dfs序中的下标
//所以p[u]+k-1刚好就是第k个数的编号
}
return 0;
}