Advertisement
Guest User

Untitled

a guest
Jan 21st, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define mx 100006
  5. #define ll long long int
  6. vector<ll>vec[mx];
  7. ll p[mx][23],d[mx],t[mx],u,v,n;
  8. bool vis[mx];
  9. void dfs(ll s,ll dep)
  10. {
  11.     for(int i=0;i<vec[s].size();i++){
  12.         ll x=vec[s][i];
  13.         if(vis[x]==false){
  14.             t[x]=s;
  15.             d[x]=dep+1;
  16.             vis[x]=true;
  17.             dfs(x,dep+1);
  18.         }
  19.     }
  20. }
  21. void init()
  22. {
  23.     memset(p,-1,sizeof(p));
  24.     for(int i=1;i<=n;i++){
  25.         p[i][0]=t[i];
  26.     }
  27.  
  28.     for(int i=0;i<18;i++){
  29.         for(int j=1;j<=n;j++){
  30.             if(p[j][i-1]!=-1){
  31.                 p[j][i]=p[p[j][i-1]][i-1];
  32.             }
  33.         }
  34.     }
  35. }
  36. void query( int u, int v)
  37.   {
  38.       if(d[v]<d[u]){
  39.         swap(u,v);
  40.     }
  41.     int dif=d[v]-d[u];
  42.     int lev;
  43.     while(1){
  44.         if(d[u]==d[v]){
  45.             break;
  46.         }
  47.         else{
  48.             v=p[v][0];
  49.         }
  50.     }
  51.     if(u==v){
  52.         printf("%lld\n",u);
  53.     }
  54.     else{
  55.         int x=t[u];
  56.         for(int i=18;i>=0;i--){
  57.             if(p[v][i]!=p[u][i]){
  58.                 v=p[v][i];
  59.                 u=p[u][i];
  60.             }
  61.         }
  62.         printf("%d\n",t[v]);
  63.     }
  64. }
  65. int main()
  66. {
  67.     ll tt,c=1;
  68.     scanf("%lld",&tt);
  69.     while(tt--){
  70.         memset(vis,false,sizeof(vis));
  71.         memset(p,0,sizeof(p));
  72.         memset(vec,0,sizeof(vec));
  73.         memset(t,0,sizeof(t));
  74.         memset(d,0,sizeof(d));
  75.         scanf("%lld",&n);
  76.         for(int i=1;i<=n;i++){
  77.             ll m;
  78.             scanf("%lld",&m);
  79.             for(int j=0;j<m;j++){
  80.                 ll a;
  81.  
  82.                 scanf("%lld",&a);
  83.                 vec[i].push_back(a);
  84.             }
  85.         }
  86.         d[1]=0;
  87.         t[1]=-1;
  88.         dfs(1,0);
  89.         init();
  90.         ll q;
  91.         printf("Case %lld:\n",c++);
  92.         scanf("%lld",&q);
  93.         while(q--){
  94.             ll a,b;
  95.  
  96.             scanf("%lld%lld",&a,&b);
  97.             query(a,b);
  98.         }
  99.     }
  100. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement