fork download 
  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.     for (long long i=LOG-1; i>=0; i--)
  23.     {
  24.         if(d[par[u][i]]>=d[v])
  25.         {
  26.             u=par[u][i];
  27.         }
  28.     }
  29.     if(u==v) return u;
  30.  
  31.     for (long long i=LOG-1; i>=0; i--)
  32.     {
  33.         if(par[u][i]!=par[v][i])
  34.         {
  35.             u=par[u][i];
  36.             v=par[v][i];
  37.         }
  38.     }
  39.     return par[u][0];
  40. }
  41. void input()
  42. {
  43.     cin >> n >> q;
  44.     for (long long i=1; i<n; i++)
  45.     {
  46.         long long u,v;
  47.         cin >> u >> v;
  48.         vt[u].push_back(v);
  49.         vt[v].push_back(u);
  50.     }
  51. }
  52. void solve()
  53. {
  54.     dfs(1);
  55.     for (long long j=1; j<LOG; j++)
  56.     {
  57.         for (long long i=1; i<=n; i++)
  58.         {
  59.             par[i][j]=par[par[i][j-1]][j-1];
  60.         }
  61.     }
  62.     d[0]=-1;
  63.     for (long long i=1; i<=q; i++)
  64.     {
  65.         long long u,v, w;
  66.         cin >> u >> v >> w;
  67.        long long l = lca(u,v);
  68.         long long len1 = d[u]-d[l];
  69.         long long len = d[u]+d[v]-2*d[l];
  70.  
  71.         if(w<=len1)
  72.         {
  73.             for(long long i=0; i<LOG; i++)
  74.             {
  75.                 if((w>>i)&1)
  76.                 {
  77.                     u=par[u][i];
  78.                 }
  79.             }
  80.             cout << u << "\n";
  81.         }
  82.         else
  83.         {
  84.             if(w>=len)
  85.             {
  86.                 cout << v << "\n";
  87.                 continue;
  88.             }
  89.  
  90.             long long new_w = len-w;
  91.  
  92.             for(long long i=0; i<LOG; i++)
  93.             {
  94.                 if((new_w>>i)&1)
  95.                 {
  96.                     v=par[v][i];
  97.                 }
  98.             }
  99.  
  100.             cout << v << "\n";
  101.         }
  102.     }
  103.  
  104. }
  105. int main()
  106. {
  107.     input();
  108.     solve();
  109. }
Success #stdin #stdout 0.01s 6688KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/q4DHVE
language:
C++14 (gcc 8.3)
created:
2 days 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!