fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair<int, int> ii;
  7.  
  8. const int INF = 1e9;
  9. const ll LINF = 1e18;
  10.  
  11. const int N = 2e5 + 5;
  12. const int LOG = 18;
  13.  
  14. int n, q;
  15. vector<int> adj[N];
  16.  
  17. int depth[N]; // depth[u] = Độ sâu của đỉnh u
  18. int up[LOG][N]; // up[i][u] = Tổ tiên thứ 2^i của u
  19.  
  20. void dfs(int u, int p) {
  21. up[0][u] = p;
  22. for (int i = 1; i < LOG; i++) {
  23. up[i][u] = up[i - 1][up[i - 1][u]];
  24. }
  25.  
  26. for (int v : adj[u]) {
  27. if (v == p) continue;
  28. depth[v] = depth[u] + 1;
  29. dfs(v, u);
  30. }
  31. }
  32.  
  33. // Tổ tiên thứ k của u
  34. int findKthAncestor(int u, int k) {
  35. if (k > depth[u]) return -1;
  36. for (int i = 0; i < LOG; i++) {
  37. if ((k >> i) & 1) {
  38. u = up[i][u];
  39. }
  40. }
  41. return u;
  42. }
  43.  
  44. int main() {
  45. ios::sync_with_stdio(false);
  46. cin.tie(nullptr);
  47. cin >> n >> q;
  48.  
  49. for (int u = 2; u <= n; u++) {
  50. int p; cin >> p;
  51. adj[u].push_back(p);
  52. adj[p].push_back(u);
  53. }
  54.  
  55. depth[1] = 0;
  56. dfs(1, 1);
  57.  
  58. while (q--) {
  59. int u, k;
  60. cin >> u >> k;
  61. cout << findKthAncestor(u, k) << '\n';
  62. }
  63. }
Success #stdin #stdout 0.01s 21596KB
stdin
5 3
1 1 3 3
4 1
4 2
4 3
stdout
3
1
-1