CodeForces 1006E Military Problem（DFS，树的选择性遍历）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 #define Bug cout<<"---------------------"<<endl
18 const int maxm=1e6+10;
19 const int maxn=2e5+10;
20 using namespace std;
21 
22 int n,m,u,k;
23 vector<int>vt[maxn];//存边
24 int son[maxn];//son[i]表示编号为i的点自身+孩子结点的总个数 
25 int rk[maxn];//rk[i]表示遍历次序为i的点的编号 
26 int sa[maxn];//sa[i]表示编号为i的点遍历的次序 
27 int cnt;//遍历次序计数器 
28 
29 void dfs(int num)
30 {
31     ++cnt;
32     rk[cnt]=num;
33     sa[num]=cnt;
34     int sum=1;
35     for(vector<int>::iterator it=vt[num].begin();it!=vt[num].end();it++)
36     {
37         int v=*it;
38         dfs(v);
39         sum+=son[v];
40     }
41     son[num]=sum;
42 }
43 
44 int main()
45 {
46     int n,m;
47     scanf("%d %d",&n,&m);
48     for(int i=2;i<=n;i++)
49     {
50         int t;
51         scanf("%d",&t);
52         vt[t].push_back(i);
53     }
54     dfs(1);//预处理 
55     for(int i=0;i<m;i++)
56     {
57         scanf("%d %d",&u,&k);
58         if(son[u]<k)//孩子数小于k 
59             printf("-1\n");
60         else
61             printf("%d\n",rk[sa[u]+k-1]);
62     }
63     return 0;
64 }