peltorator

Linear Memory Binary Liftings LCA

May 17th, 2021
879
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.  
  39.     int findLCA(int v, int u) {
  40.         if (depth[v] > depth[u]) {
  41.             v = findLA(v, depth[v] - depth[u]);
  42.         } else {
  43.             u = findLCA(u, depth[u] - depth[v]);
  44.         }
  45.         while (v != u) {
  46.             if (jump[v] != jump[u]) {
  47.                 v = jump[v];
  48.                 u = jump[u];
  49.             } else {
  50.                 v = parent[v];
  51.                 u = parent[u];
  52.             }
  53.         }
  54.         return v;
  55.     }
  56. } linearBinups;
  57.  
  58. int main() {
  59.     ios::sync_with_stdio(0);
  60.     cin.tie(0);
  61.  
  62.     int n;
  63.     cin >> n;
  64.     linearBinups.init(n);
  65.  
  66.     for (int i = 1; i < n; i++) {
  67.         int par;
  68.         cin >> par; // par < i
  69.         linearBinups.addLeaf(i, par - 1);
  70.     }
  71.  
  72.     int q;
  73.     cin >> q;
  74.     for (int i = 0; i < q; i++) {
  75.         int v, u;
  76.         cin >> v >> u;
  77.         cout << linearBinups.findLCA(v - 1, u - 1) << '\n';
  78.     }
  79. }
RAW Paste Data