CF1006E Military Problem

题意：给你一棵树，有q次查询，每次查询第n个结点的他的子树按照dfs序第x个元素是什么？

题解：一道dfs序的裸的题目。

首先需要一个数组存放第i个结点在dfs序中的位置
再需要一个数组来存放dfs序的顺序
在需要一个数组来存放一个结点子树的大小。（用来判断是否需要输出-1）

每次查询首先判断他的子树大小是否符合要求
如果符合要求再找到这个结点在dfs序中的位置。
然后利用存放dfs序顺序的数组瞬移 k-1 位，输出此元素即可。
利用这三个数组，即可再O(n)的时间复杂度下解决问题。

/*Keep on going Never give up*/
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define int long long

#define endl '\n'
#define Accepted 0
#define AK main()
#define I_can signed
using namespace std;
const int maxn =2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll mod=1e9+7;

vector<int> edge[maxn];
int num[maxn];
int sum[maxn];
int cnt=0;
vector<int> ans;
int now;
void dfs(int x){
    num[x]=++cnt;
    int t=now;
    ans.push_back(x);
    for(auto i:edge[x]){
        now++;
        dfs(i);
    }
    sum[x]=now-t;
}

signed main(){
    int n,m;
    ios::sync_with_stdio(false);
    cin>>n>>m;
    ans.push_back(-1);
    for(int i=2;i<=n;i++){
        int x;
        cin>>x;
        edge[x].push_back(i);
    }
    dfs(1);
    for(int i=0;i<m;i++){
        int x,k;
        cin>>x>>k;
        int pos=num[x];
        if(k-1>sum[x]) cout<<-1<<endl;
        else
        cout<<ans[pos+k-1]<<endl;
    }
}