fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxN = 1e5 + 5, LOG= 17;
  4. long long n,q, par[MaxN][LOG], d[MaxN];
  5. vector<long long> vt[MaxN];
  6. void dfs(long long u)
  7. {
  8.     for(long long v : vt[u])
  9.     {
  10.         if(v!=par[u][0])
  11.         {
  12.             par[v][0]=u;
  13.             d[v]=d[u]+1;
  14.             dfs(v);
  15.         }
  16.     }
  17. }
  18. long long lca(long long u, long long v)
  19. {
  20.     if(d[u]<d[v]) swap(u,v);
  21.  
  22.  
  23.     for (long long i=LOG-1; i>=0; i--)
  24.     {
  25.         if(d[par[u][i]]>=d[v])
  26.         {
  27.             u=par[u][i];
  28.         }
  29.     }
  30.     if(u==v) return u;
  31.  
  32.     for (long long i=LOG-1; i>=0; i--)
  33.     {
  34.         if(par[u][i]!=par[v][i])
  35.         {
  36.             u=par[u][i];
  37.             v=par[v][i];
  38.         }
  39.     }
  40.     return par[u][0];
  41. }
  42. void input()
  43. {
  44.     cin >> n >> q;
  45.     for (long long i=1; i<n; i++)
  46.     {
  47.         long long u,v;
  48.         cin >> u >> v;
  49.         vt[u].push_back(v);
  50.         vt[v].push_back(u);
  51.     }
  52. }
  53. void solve()
  54. {
  55.     dfs(1);
  56.     for (long long j=1; j<LOG; j++)
  57.     {
  58.         for (long long i=1; i<=n; i++)
  59.         {
  60.             par[i][j]=par[par[i][j-1]][j-1];
  61.         }
  62.     }
  63.     d[0]=-1;
  64.     for (long long i=1; i<=q; i++)
  65.     {
  66.         long long u,v;
  67.         cin >> u >> v;
  68.         cout << lca(u,v) << "\n";
  69.     }
  70.  
  71. }
  72. int main()
  73. {
  74.     input();
  75.     solve();
  76. }
Success #stdin #stdout 0.01s 7036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/lfoPMB
language:
C++14 (gcc 8.3)
created:
16 hours 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!