SHARE
TWEET

LCA using Segment Tree

amstan Jul 18th, 2019 (edited) 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //LCA using Segment Tree
  2. //https://www.spoj.com/problems/LCA/
  3. #include <iostream>
  4. #include <sstream>
  5. #include <cstdio>
  6. #include <cmath>
  7. #include <cstring>
  8. #include <cctype>
  9. #include <string>
  10. #include <vector>
  11. #include <list>
  12. #include <set>
  13. #include <map>
  14. #include <queue>
  15. #include <stack>
  16. #include <algorithm>
  17. #include <functional>
  18. using namespace std;
  19. typedef long long ll;
  20.  
  21. #define mem(dp,a)           memset(dp,a,sizeof dp)
  22. #define rep(i,a,b)          for(ll i=a;i<b;i++)
  23. #define pb(x)               push_back(x)
  24. #define mp(x,y)             make_pair(x,y)
  25. #define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
  26. #define F                   first
  27. #define S                   second
  28. #define all(v)              (v).begin(),(v).end()
  29. #define pi                  3.14159265359
  30. ll INF=1e18+10;
  31. ll MOD=1000000009;
  32.  
  33. const int N=1e4+10;
  34. vector<int> euler,adj[N];
  35. int first[N],segt[4*N],height[N];
  36. bool vis[N];
  37.  
  38. void dfs(int v,int h=0)
  39. {
  40.     vis[v]=true;euler.push_back(v);
  41.     first[v]=euler.size()-1,height[v]=h;
  42.     for(auto to : adj[v])
  43.         if(!vis[to])
  44.             dfs(to,h+1),euler.push_back(v);
  45. }
  46.  
  47. void build(int l,int r,int v)
  48. {
  49.     if(l==r)
  50.         segt[v]=euler[l];
  51.     else
  52.     {
  53.         int mid=(l+r)>>1;
  54.         build(l,mid,v<<1);
  55.         build(mid+1,r,v<<1|1);
  56.         int left=segt[v<<1],right=segt[v<<1|1];
  57.         segt[v]=(height[left]<height[right]) ? left : right;
  58.     }
  59. }
  60.  
  61. int query(int v,int l,int r,int L,int R)
  62. {
  63.     if(l>R || r<L)
  64.         return -1;
  65.     if(l<=L && R<=r)
  66.         return segt[v];
  67.     int mid=(L+R)>>1;
  68.     int left=query(v<<1,l,r,L,mid);
  69.     int right=query(v<<1|1,l,r,mid+1,R);
  70.     if(left==-1)return right;
  71.     if(right==-1)return left;
  72.     return (height[left]<height[right]) ? left : right;
  73. }
  74.  
  75. int lca(int u,int v)
  76. {
  77.     int left=first[u],right=first[v];
  78.     if(left>right)swap(left,right);
  79.     return query(1,left,right,1,euler.size()-1);
  80. }
  81.  
  82. int main()
  83. {
  84.     fastio;
  85.     int t;cin>>t;
  86.     for(int j=1;j<=t;j++)
  87.     {
  88.         cout<<"Case "<<j<<":\n";
  89.         mem(segt,0);mem(vis,0);mem(first,0);mem(height,0);
  90.         euler.clear();euler.push_back(-1);
  91.         for(int i=0;i<N;i++)adj[i].clear();
  92.         int n;cin>>n;
  93.         for(int i=1;i<=n;i++)
  94.         {
  95.             int m;cin>>m;
  96.             int b;
  97.             for(int j=0;j<m;j++)
  98.                 cin>>b,adj[i].push_back(b);
  99.         }
  100.         dfs(1,0);
  101.         build(1,euler.size()-1,1);
  102.         int q;cin>>q;
  103.         while(q--)
  104.         {
  105.             int u,v;cin>>u>>v;
  106.             cout<<lca(u,v)<<"\n";
  107.         }
  108.     }
  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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top