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 a,b,c;
  67.         cin >> a >> b >> c;
  68.         long long l_ab = lca(a,b);
  69.         long long l_bc = lca(b,c);
  70.         long long l_ca = lca(c,a);
  71.         long long mx = max({d[l_ab],d[l_bc],d[l_ca]});
  72.         if(d[l_ab]==mx)
  73.         {
  74.             cout << l_ab << "\n";
  75.         }
  76.         else if(d[l_bc]==mx)
  77.         {
  78.             cout << l_bc << "\n";
  79.         }
  80.         else if(d[l_ca]==mx)
  81.         {
  82.             cout << l_ca << "\n";
  83.         }
  84.     }
  85.  
  86. }
  87. int main()
  88. {
  89.     input();
  90.     solve();
  91. }
Success #stdin #stdout 0.01s 6240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/GIfTxT
language:
C++14 (gcc 8.3)
created:
1 day 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!