Military Problem(DFS序)

题目大意：
给你一棵树，然后有q个询问(u,k),问以u为根进行深度优先搜索第k个元素是多少？
思路：
朴素做法：对于q个询问，每个询问dfs一下求第k个元素即可。---超时
正解：
我们可以先求出以1为根的所有节点的dfs序，然后记录一下第i个dfs序是谁，然后对于q个询问输出第(dfn[u] + k - 1)个dfs序是谁即可。
对于-1的情况，我们只需要开一个数组记录每颗子树儿子的数量，然后如果k > son[u]输出-1即可。
代码：

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 2e6 + 10;
vector<int>G[maxn];
int dfn[maxn],tot;
int ans[maxn],son[maxn];
void dfs(int u,int fu){
    dfn[u] = ++tot;
    ans[tot] = u;
    son[u] = 1;
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v != fu){
            dfs(v,u);
            son[u] += son[v];
        }
    }
}
void solved(){
    int n,q;scanf("%d%d",&n,&q);
    for(int i = 2; i <= n; i++){
        int u;scanf("%d",&u);
        G[i].push_back(u);
        G[u].push_back(i);
    }
    dfs(1,0);
    while(q--){
        int u,k;scanf("%d%d",&u,&k);
        if(k > son[u]){puts("-1");continue;}
        printf("%d\n",ans[dfn[u] + k - 1]);
    }
}
int main(){
    solved();
    return 0;
}