【每日一题】dfs序专题 Military Problem

Description

一句话翻译(祈福12月六级考试)
给一棵树,m个查询
每个查询(u, k) 代表 u 节点dfs序下第k个节点

Solution

令l[i] 表示i节点的起点位置，r[i] 表示i节点的终止位置，a[i] 表示第i个数字是哪个节点。
对于每个查询，查找是否在 [l[u], r[u]]区间内，不在的话输出-1，否则输出a[l[u] + k - 1]。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
vector<int> G[N];
int tot, a[N], l[N], r[N];
void dfs(int u) {
  ++tot;
  a[tot] = u;
  l[u] = tot;
  for(auto &x : G[u]) {
    dfs(x);
  }
  r[u] = tot;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, m; cin >> n >> m;
  for(int i = 2; i <= n; i++) {
    int u; cin >> u;
    G[u].push_back(i);
  }
  dfs(1);
  while(m--) {
    int val, dis; cin >> val >> dis;
    int pos = l[val] + dis - 1;
    if(pos > r[val]) {
      cout << -1 << '\n';
    } else {
      cout << a[pos] << '\n';
    }
  }
  return 0;
}