peltorator

Linear Memory Binary Liftings LA

May 17th, 2021 (edited)
250
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct LinearBinups {
  6.     vector<int> depth;
  7.     vector<int> parent;
  8.     vector<int> jump;
  9.  
  10.     void init(int n, int root = 0) {
  11.         depth.assign(n, 0);
  12.         parent.assign(n, 0);
  13.         jump.assign(n, 0);
  14.         parent[root] = jump[root] = root;
  15.     }
  16.  
  17.     void addLeaf(int v, int par) {
  18.         parent[v] = par;
  19.         depth[v] = depth[par] + 1;
  20.         if (depth[par] - depth[jump[par]] == depth[jump[par]] - depth[jump[jump[par]]]) {
  21.             jump[v] = jump[jump[par]];
  22.         } else {
  23.             jump[v] = par;
  24.         }
  25.     }
  26.  
  27.     int findLA(int v, int k) {
  28.         int h = max(depth[v] - k, 0);
  29.         while (depth[v] != h) {
  30.             if (depth[jump[v]] >= h) {
  31.                 v = jump[v];
  32.             } else {
  33.                 v = parent[v];
  34.             }
  35.         }
  36.         return v;
  37.     }
  38. } linearBinups;
  39.  
  40. int main() {
  41.     ios::sync_with_stdio(0);
  42.     cin.tie(0);
  43.  
  44.     int n;
  45.     cin >> n;
  46.     linearBinups.init(n);
  47.  
  48.     for (int i = 1; i < n; i++) {
  49.         int par;
  50.         cin >> par; // par < i
  51.         linearBinups.addLeaf(i, par - 1);
  52.     }
  53.  
  54.     int q;
  55.     cin >> q;
  56.     for (int i = 0; i < q; i++) {
  57.         int v, k;
  58.         cin >> v >> k;
  59.         cout << linearBinups.findLA(v - 1, k) << '\n';
  60.     }
  61. }
RAW Paste Data