fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5. const long long LOG = 20;
  6.  
  7. long long n,q;
  8. long long par[MaxN][LOG];
  9. long long mx[MaxN][LOG];
  10. long long d[MaxN];
  11.  
  12. vector<pair<long long,long long>> vt[MaxN];
  13. pair<long long,long long> pr[MaxN];
  14.  
  15. void dfs(long long u)
  16. {
  17.     for(auto x : vt[u])
  18.     {
  19.         long long v = x.first;
  20.         long long w = x.second;
  21.  
  22.         if(v == par[u][0])
  23.             continue;
  24.  
  25.         par[v][0] = u;
  26.         mx[v][0] = w;
  27.         d[v] = d[u] + 1;
  28.  
  29.         dfs(v);
  30.     }
  31. }
  32.  
  33. void build()
  34. {
  35.     for(long long j = 1; j < LOG; j++)
  36.     {
  37.         for(long long i = 1; i <= n; i++)
  38.         {
  39.             par[i][j] = par[par[i][j-1]][j-1];
  40.  
  41.             mx[i][j] = max(mx[i][j-1],
  42.                            mx[par[i][j-1]][j-1]);
  43.         }
  44.     }
  45. }
  46.  
  47. long long get_max(long long u, long long anc)
  48. {
  49.     long long ans = 0;
  50.  
  51.     long long diff = d[u] - d[anc];
  52.  
  53.     for(long long i = LOG-1; i >= 0; i--)
  54.     {
  55.         if((diff >> i) & 1)
  56.         {
  57.             ans = max(ans, mx[u][i]);
  58.             u = par[u][i];
  59.         }
  60.     }
  61.  
  62.     return ans;
  63. }
  64.  
  65. long long lca(long long u, long long v)
  66. {
  67.     if(d[u] < d[v])
  68.         swap(u,v);
  69.  
  70.     for(long long i = LOG-1; i >= 0; i--)
  71.     {
  72.         if(d[par[u][i]] >= d[v])
  73.             u = par[u][i];
  74.     }
  75.  
  76.     if(u == v)
  77.         return u;
  78.  
  79.     for(long long i = LOG-1; i >= 0; i--)
  80.     {
  81.         if(par[u][i] != par[v][i])
  82.         {
  83.             u = par[u][i];
  84.             v = par[v][i];
  85.         }
  86.     }
  87.  
  88.     return par[u][0];
  89. }
  90.  
  91. void input()
  92. {
  93.     cin >> n >> q;
  94.  
  95.     for(long long i = 1; i < n; i++)
  96.     {
  97.         long long u,v,w;
  98.         cin >> u >> v >> w;
  99.  
  100.         vt[u].push_back({v,w});
  101.         vt[v].push_back({u,w});
  102.     }
  103.  
  104.     for(long long i = 1; i <= q; i++)
  105.     {
  106.         cin >> pr[i].first >> pr[i].second;
  107.     }
  108. }
  109.  
  110. void solve()
  111. {
  112.     d[0] = -1;
  113.  
  114.     dfs(1);
  115.     build();
  116.  
  117.     for(long long i = 1; i <= q; i++)
  118.     {
  119.         long long u = pr[i].first;
  120.         long long v = pr[i].second;
  121.  
  122.         long long l = lca(u,v);
  123.  
  124.         long long ans1 = get_max(u,l);
  125.         long long ans2 = get_max(v,l);
  126.  
  127.         cout << max(ans1,ans2) << '\n';
  128.     }
  129. }
  130.  
  131. int main()
  132. {
  133.     ios_base::sync_with_stdio(0);
  134.     cin.tie(0);
  135.  
  136.     input();
  137.     solve();
  138. }
Success #stdin #stdout 0s 7524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6OTD87
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!