bhupixb

Lowest common Ancestor RMQ segment tree

Jul 27th, 2018
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.37 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. typedef long long int ll;
  4. const int N = 1 << 10;
  5. #define pb(x) push_back(x);
  6. #define L cout << '\n'
  7. vector < int > tree(N), v[N], euler(1),vis(N), ht(N), indx(N);
  8. void Euler_tour(int node, int height){
  9. vis[node] = true;
  10. ht[node] = height ;
  11. euler.pb(node);
  12.  
  13. for(auto i : v[node]){
  14. if(!vis[i]){
  15. Euler_tour(i, height + 1);
  16. euler.pb(node);
  17. }
  18. }
  19. }
  20. void build(int l, int r, int node){
  21. if(l == r){
  22. tree[node] = euler[l];
  23. return;
  24. }
  25. int mid = l + r >> 1;
  26.  
  27. build(l, mid, 2 * node);
  28. build(mid + 1, r, 2 * node + 1);
  29. if(ht[tree[2 * node]] < ht[tree[2 * node + 1]])
  30. tree[node] = tree[2 * node];//,cout << euler[2*node] << ' ';
  31. else
  32. tree[node] = tree[2 * node + 1];//,cout << euler[2*node + 1] << ' ';
  33. }
  34. int query(int l, int r, int ql, int qr, int node){
  35. if(r < ql || l > qr)return -1;
  36.  
  37. if(ql <= l && r <= qr)return tree[node];
  38.  
  39. int mid = (l + r) >> 1;
  40. int x = query(l, mid, ql, qr, 2 * node);
  41. int y = query(mid + 1, r, ql , qr, 2 * node + 1);
  42. if(x == -1)return y;
  43. if(y == -1)return x;
  44. //cout << l << ' ' << r << ' ' << x << ' ' << y;L;
  45. if(ht[x] < ht[y])return x;
  46. else return y;
  47. }
  48. int main(){
  49. ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  50. int n, l, r, i, x, y, q;
  51. cin >> n;
  52. cout << n << ' ';L;
  53. for(i = 0; i < n-1; i++){
  54. cin >> l >> r;
  55. v[l].pb(r);
  56. v[r].pb(l);
  57. }
  58.  
  59. Euler_tour(1, 0);
  60. for(i = 1; i < euler.size(); i++){
  61. if(!indx[euler[i]]){
  62. indx[euler[i]] = i;
  63. }
  64. }
  65.  
  66. //for(i =1; i < euler.size(); i++)cout << euler[i] << ' ';
  67. //L;
  68. //for(i = 1; i <= n; i++)
  69. // cout << ht[i] << ' ';
  70. // It's time build segment tree
  71. //L;
  72. //for(i = 1; i <= n; i++)cout << indx[i] << ' ';
  73. //L;
  74.  
  75. build(1, (int)euler.size() - 1, 1);
  76. cin >> q;
  77. while(q--){
  78. cin >> x >> y;
  79. //cout << x << ' ' << y;L;
  80. l = indx[x], r = indx[y];
  81. if(l > r)swap(l,r);
  82. //cout << l << ' ' << r;L;
  83. cout << query(1, (int)euler.size()-1 , l, r, 1);L;
  84. }
  85.  
  86.  
  87.  
  88.  
  89.  
  90. return 0;
  91. }
Add Comment
Please, Sign In to add comment