fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5.  
  6. ll L[100];
  7. ll P[100][20];
  8. ll T[100];
  9. vector<ll>graph[100];
  10.  
  11. void dfs(ll src,ll par)
  12. {
  13.     if(src==-1)
  14.         L[par]=1;
  15.     else
  16.         L[par]=L[src]+1;
  17.     T[par]=src;
  18.     ll len=graph[par].size();
  19.     for(ll i=0; i<(ll)graph[par].size(); i++)
  20.     {
  21.         ll v=graph[par][i];
  22.         if(v!=src)
  23.         {
  24.             dfs(par,v);
  25.         }
  26.     }
  27. }
  28.  
  29. ll query(ll n,ll p,ll q)
  30. {
  31.     ll log=1,i,j,temp;
  32.     if(L[p]<L[q])
  33.     {
  34.         temp=q;
  35.         q=p;
  36.         p=temp;
  37.     }
  38.  
  39.     log=log2(n);
  40.  
  41.     for(j=log; j>=0; j--)
  42.     {
  43.         if(L[p]-(1<<j)>=L[q])
  44.         {
  45.             p=P[p][j];
  46.         }
  47.     }
  48.  
  49.     if(p==q)
  50.         return p;
  51.  
  52.     for(j=log; j>=0; j--)
  53.     {
  54.         if(P[p][j]!=-1&&P[p][j]!=P[q][j])
  55.             p=P[p][j],q=P[q][j];
  56.     }
  57.     return T[p];
  58. }
  59.  
  60.  
  61. void lca(ll n)
  62. {
  63.     memset(P,-1,sizeof(P));
  64.     ll i,j;
  65.     for(i=1; i<=n; i++)
  66.         P[i][0]=T[i];
  67.     for(j=1; (1<<j)<n; j++)
  68.     {
  69.         for(i=1; i<=n; i++)
  70.         {
  71.             if(P[i][j-1]!=-1)
  72.             {
  73.                 P[i][j]=P[P[i][j-1]][j-1];
  74.             }
  75.         }
  76.     }
  77. }
  78.  
  79. int main()
  80. {
  81.     ll i,j,n,m,t,a,b;
  82.     scanf("%lld",&n);
  83.     for(i=0; i<n-1; i++)
  84.     {
  85.         scanf("%lld%lld",&a,&b);
  86.         graph[a].push_back(b);
  87.         graph[b].push_back(a);
  88.     }
  89.     dfs(-1,1);
  90.     lca(n);
  91.  
  92.     cin>>a>>b;
  93.     cout<<query(n,a,b)<<endl;
  94. }
  95.  
  96.  
Runtime error #stdin #stdout 0s 4968KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9JjVIz
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!