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], weight[MaxN];
  5. vector<pair<long long,long long>> vt[MaxN];
  6. void dfs(long long u)
  7. {
  8.     for(auto x  : vt[u])
  9.     {
  10.         long long v = x.first, weight_v=x.second;
  11.         if(v!=par[u][0])
  12.         {
  13.             par[v][0]=u;
  14.             d[v]=d[u]+1;
  15.             weight[v]=weight[u]+weight_v;
  16.             dfs(v);
  17.         }
  18.     }
  19. }
  20. long long lca(long long u, long long v)
  21. {
  22.     if(d[u]<d[v]) swap(u,v);
  23.  
  24.     for (long long i=LOG-1; i>=0; i--)
  25.     {
  26.         if(d[par[u][i]]>=d[v])
  27.         {
  28.             u=par[u][i];
  29.         }
  30.     }
  31.     if(u==v) return u;
  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, w;
  48.         cin >> u >> v >> w;
  49.         vt[u].push_back({v,w});
  50.         vt[v].push_back({u,w});
  51.     }
  52. }
  53. void solve()
  54. {
  55.     d[0]=-1;
  56.     dfs(1);
  57.     for (long long j=1; j<LOG; j++)
  58.     {
  59.         for (long long i=1; i<=n; i++)
  60.         {
  61.             par[i][j]=par[par[i][j-1]][j-1];
  62.         }
  63.     }
  64.     for (long long i=1; i<=q; i++)
  65.     {
  66.         long long u,v;
  67.         cin >> u >> v;
  68.         cout << weight[u]+weight[v]-2*weight[lca(u,v)] << "\n";
  69.     }
  70.  
  71. }
  72. int main()
  73. {
  74.     input();
  75.     solve();
  76. }
Success #stdin #stdout 0.01s 7292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/X5zxYp
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!