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.     //cân bằng độ sâu
  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.     //cùng đi lên
  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, w;
  67.         cin >> u >> v >> w;
  68.        long long l = lca(u,v);
  69.         long long len1 = d[u]-d[l];
  70.         long long len = d[u]+d[v]-2*d[l];
  71.  
  72.         if(w<=len1)
  73.         {
  74.             for(long long i=0; i<LOG; i++)
  75.             {
  76.                 if((w>>i)&1)
  77.                 {
  78.                     u=par[u][i];
  79.                 }
  80.             }
  81.             cout << u << "\n";
  82.         }
  83.         else
  84.         {
  85.             if(w>=len)
  86.             {
  87.                 cout << v << "\n";
  88.                 continue;
  89.             }
  90.  
  91.             long long new_w = len-w;
  92.  
  93.             for(long long i=0; i<LOG; i++)
  94.             {
  95.                 if((new_w>>i)&1)
  96.                 {
  97.                     v=par[v][i];
  98.                 }
  99.             }
  100.  
  101.             cout << v << "\n";
  102.         }
  103.     }
  104.  
  105. }
  106. int main()
  107. {
  108.     input();
  109.     solve();
  110. }
  111.  
Success #stdin #stdout 0.01s 7028KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/q2l6bK
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!