SHARE
TWEET

LCA

a guest Dec 14th, 2019 148 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int n;
  5. vector<int> adj[400009];
  6. int parent[400009], level[400009], anc[400009][21];
  7.  
  8. void dfs(int node, int pr, int l)
  9. {
  10.     parent[node] = pr;
  11.     level[node] = l;
  12.  
  13.     for(auto u : adj[node])
  14.     {
  15.         if(u != parent[node])
  16.             dfs(u, node, l+1);
  17.     }
  18. }
  19.  
  20. void lca()
  21. {
  22.     dfs(1, 1, 0);
  23.  
  24.     int i, j;
  25.     for(i = 1; i <= n; i++)
  26.     {
  27.         for(j = 0; (1 << j) < n; j++)
  28.             anc[i][j] = 1;
  29.     }
  30.     for(i = 1; i <= n; i++)
  31.         anc[i][0] = parent[i];
  32.  
  33.     for(j = 1; (1<<j) < n; j++)
  34.     {
  35.         for(i = 1; i <= n; i++)
  36.             anc[i][j] = anc[anc[i][j-1]][j-1];
  37.     }
  38. }
  39.  
  40. int query(int u, int v)
  41. {
  42.     if(level[u] < level[v])
  43.         swap(u, v);
  44.  
  45. //    cout << u << " " << v << endl;
  46.  
  47.     int i;
  48.     for(i = log2(n) + 1; i >= 0; i--)
  49.     {
  50.         if(level[anc[u][i]] >= level[v])
  51.             u = anc[u][i];
  52.     }
  53.  
  54. //    cout << u << " " << v << endl;
  55.  
  56.     if(u == v)
  57.         return u;
  58.     for(i = log2(n) + 1; i >= 0; i--)
  59.     {
  60.         if(anc[u][i] != anc[v][i])
  61.         {
  62.             u = anc[u][i];
  63.             v = anc[v][i];
  64.         }
  65.     }
  66.  
  67.     return parent[u];
  68. }
  69.  
  70.  
  71.  
  72. int main()
  73. {
  74.     int i, u, v;
  75.     cin >> n;
  76.  
  77.     for(i = 1; i <= n-1; i++)
  78.     {
  79.         cin >> u >> v;
  80.         adj[u].push_back(v);
  81.         adj[v].push_back(u);
  82.     }
  83.  
  84.     lca();
  85.  
  86.     int q;
  87.     cin >> q;
  88.     while(q--)
  89.     {
  90.         cin >> u >> v;
  91. //        cout << level[u] << " " << level[v] << endl;
  92. //        cout << anc[7][0] << endl;
  93.         cout << query(u, v) << endl;
  94.     }
  95. }
  96. /*
  97. 10
  98. 1 3
  99. 1 7
  100. 3 2
  101. 3 10
  102. 2 6
  103. 5 7
  104. 8 5
  105. 5 9
  106. 7 4
  107. 1
  108. 7 1
  109. */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top