Guest User

LCA

a guest
Dec 14th, 2019
159
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