nrk009

LCA of TREE

Sep 22nd, 2020
921
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //This Time Fire Is Different
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
  7. #define ll long long
  8. #define ld long double
  9. #define pb push_back
  10. #define fe first
  11. #define se second
  12. #define nl "\n"
  13. #define pp pair < ll , ll >
  14. #define sz(x) (ll)x.size()
  15. #define st(x) sort(x.begin(),x.end())
  16. #define rst(x) sort(x.rbegin(), x.rend())
  17. #define all(x) x.begin(),x.end()
  18. long double pi = 3.14159265358979323;
  19.  
  20. const double EPS = 1e-12;
  21. const int N = 1e3 + 5;
  22. const int mod = 1e9 + 7;
  23.  
  24. ll n;
  25. vector < ll > v[N];
  26. ll l ;
  27. ll up[N][11];
  28. ll tin[N] ,tout[N];
  29. ll timer;
  30. void dfs(ll s , ll p){
  31.  
  32.     up[s][0] = p;
  33.     tin[s] = timer++;
  34.     for(int i = 1 ; i <= l ; i++ ){
  35.         up[s][i] = up[up[s][i-1]][i-1];
  36.     }
  37.     //vis[s] = 1;
  38.     for(auto it  :v[s]){
  39.         if(it != p){
  40.             dfs(it,s);
  41.         }
  42.     }
  43.     tout[s] = timer++;
  44. }
  45.  
  46. bool is_ances(ll u , ll v){
  47.     return (tin[u] <= tin[v] && tout[u] >= tout[v]);
  48. }
  49.  
  50. ll lca(ll u , ll v){
  51.     if(is_ances(u,v)){
  52.         return u;
  53.     }
  54.     if(is_ances(v,u)){
  55.         return v;
  56.     }
  57.  
  58.     for(int i = l ; i >= 0 ; i--){
  59.         if(!is_ances(up[u][i],v)){
  60.             u = up[u][i];
  61.         }
  62.     }
  63.     return up[u][0];
  64. }
  65.  
  66.  
  67.  
  68. int main()
  69. {
  70.     fast;
  71.     ll t;
  72.     cin >> t ;
  73.   for(int i = 1 ; i  <= t ; i++ ){
  74.         ll n;
  75.         cin >> n ;
  76.         l = log2(n);
  77.         for(int i = 1 ; i  <= n ;  i++ ){
  78.             ll m;
  79.             cin >> m;
  80.             while(m--){
  81.                 ll x;
  82.                 cin >> x ;
  83.                 v[i].pb(x);
  84.                 v[x].pb(i);
  85.             }
  86.         }
  87.         dfs(1,1);
  88.         ll q;
  89.         cin >> q ;
  90.         cout << "Case " << i << ":\n";
  91.         while(q--){
  92.             ll x , y;
  93.             cin >> x >> y ;
  94.             cout << lca(x,y) << "\n";
  95.         }
  96.         for(int i = 1 ; i  <= n ; i++ ){
  97.             v[i].clear();
  98.             //vis[i] = 0 ;
  99.             //level[i] = 0 ;
  100.             for(int j = 0  ; j < 11  ; j++ )
  101.                     up[i][j]  = 0 ;
  102.         }
  103.     }
  104.    
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.    
  127.     return 0;
  128.    
  129. }
RAW Paste Data