[Codeforces1006E] Military Problem(DFS)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：http://codeforces.com/contest/1006/problem/E

给一棵$n$个节点的树和$q$次询问，每次询问两个数$u、k$，表示第u个节点的第k个前序遍历的结果是谁。

这么水的题竟然放在了E，可能这就是div 3吧…

dfs一遍，维护出每个节点$i$的前序遍历的次序$ret_i$，以及该节点的子树中共计多少个节点$sz_i$，可以利用$ret_i$维护出第$j$号遍历的节点是$id_i$。当我们要求的某节点开始往后数$k$个数不存在时，输出-1；否则我们的答案就是$ret[id[u]+k-1]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200100;
int n, q, tot;
vector<int> G[maxn];
int ret[maxn], sz[maxn], id[maxn];

int dfs(int u, int p) {
  ret[++tot] = u;
  int son = 1;
  for(int i = 0; i < G[u].size(); i++) {
    int &v = G[u][i];
    if(v == p) continue;
    son += dfs(v, u);
  }
  return sz[u] = son;
}

signed main() {
  // freopen("in", "r", stdin);
  int u, k;
  while(~scanf("%d%d",&n,&q)) {
    tot = 0;
    memset(ret, -1, sizeof(ret));
    memset(sz, 0, sizeof(sz));
    for(int i = 1; i <= n; i++) G[i].clear();
    for(int i = 2; i <= n; i++) {
      scanf("%d",&u);
      G[i].push_back(u);
      G[u].push_back(i);
    }
    sz[1] = dfs(1, -1);
    for(int i = 1; i <= n; i++) id[ret[i]] = i;
    while(q--) {
      scanf("%d%d",&u,&k);
      if(k - 1 >= sz[u]) printf("-1\n");
      else printf("%d\n", ret[id[u]+k-1]);
    }
  }
  return 0;
}