Fshl0

LCA (Binary Lifting)

Jun 17th, 2020
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define mod 1000000007
  3. #define pb push_back
  4. #define F first
  5. #define S second
  6.  
  7. using namespace std;
  8. typedef long long ll;
  9. typedef long double ld;
  10. const double pi = acos(-1.0);
  11. const double eps = 1e-9;
  12. ll dx[4] = {0, 1, 0, -1};
  13. ll dy[4] = {1, 0, -1, 0};
  14.  
  15. const ll INF = 1e7;
  16. const int MX = 2e5 + 9;
  17. const int MN = 20;
  18.  
  19. vector <int> adj[MX];
  20. int in[MX], out[MX], t = 0, l;
  21. int up[MX][MN];
  22.  
  23. void DFS (int v, int p) {
  24.     in[v] = ++t;
  25.     up[v][0] = p;
  26.     for (int i = 1; i <= l; i++)
  27.         up[v][i] = up[up[v][i - 1]][i - 1];
  28.     for (auto u: adj[v]) {
  29.         if (u == p) continue;
  30.         DFS (u, v);
  31.     }
  32.     out[v] = ++t;
  33. }
  34.  
  35. bool chk (int u, int v) {
  36.     return (in[u] <= in[v]) && (out[u] >= out[v]);
  37. }
  38.  
  39. int lca (int u, int v) {
  40.     if (chk(u, v)) return u;
  41.     if (chk(v, u)) return v;
  42.     for (int i = l; i >= 0; i--)
  43.         if (!chk(up[u][i], v))
  44.             u = up[u][i];
  45.     return up[u][0];
  46. }
  47.  
  48. int main() {
  49.     int n, m;
  50.     cin >> n >> m;
  51.     for (int i = 1; i < n; i++) {
  52.         int u, v;
  53.         cin >> u >> v;
  54.         adj[u].pb(v);
  55.         adj[v].pb(u);
  56.     }
  57.     l = log2(n);
  58.     DFS (1, 1);
  59.     while (m--) {
  60.         int u, v;
  61.         cin >> u >> v;
  62.         cout << lca(u, v) << endl;
  63.     }
  64.     return 0;
  65. }
RAW Paste Data