Advertisement
Josif_tepe

Untitled

Mar 17th, 2024
408
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.06 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 2e5 + 10;
  5. const int logn = 18;
  6. int parent[maxn][logn];
  7. vector<int> depth(maxn, 0);
  8. int kth_ancestor(int node, int k) {
  9.     if(depth[node] < k) {
  10.         return -1;
  11.     }
  12.     for(int i = logn; i >= 0; i--) {
  13.         if(node == -1) {
  14.             break;
  15.         }
  16.         if(k & (1 << i)) {
  17.             node = parent[node][i];
  18.         }
  19.     }
  20.     return node;
  21. }
  22. int main() {
  23.     int n, q;
  24.     cin >> n >> q;
  25.     vector<int> tree(n + 1, -1);
  26.    
  27.     for(int i = 2; i <= n; i++) {
  28.         cin >> tree[i];
  29.         parent[i][0] = tree[i];
  30.     }  
  31.     tree[1] = 1;
  32.     for(int i = 1; i <= n; i++) {
  33.         if(i != 1) {
  34.             depth[i] = depth[tree[i]] + 1;
  35.         }
  36.         parent[i][0] = tree[i];
  37.         for(int j = 1; j <= logn; j++) {
  38.             parent[i][j] = parent[parent[i][j - 1]][j - 1];
  39.         }
  40.  
  41.     }    
  42.     while(q--) {
  43.         int node, k;
  44.         cin >> node >> k;
  45.         cout << kth_ancestor(node, k) << endl;
  46.     }
  47.     return 0;
  48. }
  49.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement