fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define F first
  5. #define S second
  6. #define yes cout << "YES" << "\n"
  7. #define no cout << "NO" << "\n"
  8. #define answer cout << ans1 << "\n"
  9. #define db long double
  10. using namespace std;
  11.  
  12.  
  13. ll n,m,a,b,c,d,k,w,x,y,z,ans1,q,T;
  14. bool f=0;
  15. char cc;
  16. const int N=1e5 + 10 , LOG = 20;
  17. const int mod = 998244353;
  18. vector<pair<ll,ll>> g[N];
  19. ll anc[N][LOG];
  20. ll sum[N][LOG];
  21. ll dep[N];
  22.  
  23. void dfs(int v)
  24. {
  25.   for(int i=1;i<LOG;++i)
  26.   {
  27.     anc[v][i] = anc[anc[v][i-1]][i-1];
  28.     sum[v][i] = sum[v][i-1] + sum[anc[v][i-1]][i-1];
  29.   }
  30.  
  31.   for(auto [x,c] : g[v])
  32.   {
  33.     if(x==anc[v][0]){continue;}
  34.  
  35.     dep[x] = dep[v] + 1;
  36.     anc[x][0] = v;
  37.     sum[x][0] = c;
  38.     dfs(x);
  39.   }
  40. }
  41.  
  42. ll LCA(int v,int u)
  43. {
  44.   if(dep[v]<dep[u]){swap(v,u);}
  45.   int k = dep[v] - dep[u];
  46.   ll ret = 0;
  47.   for(int i=0;i<LOG;++i)
  48.   {
  49.     if(k&(1<<i))
  50.     {
  51.       ret += sum[v][i];
  52.       v = anc[v][i];
  53.     }
  54.   }
  55.   if(v==u)
  56.   {
  57.     return ret;
  58.   }
  59.  
  60.   for(int i=LOG-1;i>=0;--i)
  61.   {
  62.     if(anc[v][i]!=anc[u][i])
  63.     {
  64.       ret += sum[v][i];
  65.       ret += sum[u][i];
  66.       v = anc[v][i];
  67.       u = anc[u][i];
  68.     }
  69.   }
  70.  
  71.   ret += sum[v][0] + sum[u][0];
  72.   return ret;
  73. }
  74.  
  75. void solve()
  76. {
  77.   cin >> n >> q;
  78.   for(int i=1;i<=n;++i){g[i].clear();}
  79.   for(int i=1;i<=n-1;++i)
  80.   {
  81.     cin >> a >> b >> c;
  82.     g[a].push_back({b,c});
  83.     g[b].push_back({a,c});
  84.   }
  85.   cin >> x >> y >> z;
  86.   dfs(1);
  87.   while(q--)
  88.   {
  89.     cin >> a >> b;
  90.     cout << min({LCA(a,b) , LCA(a,x) + LCA(b,y) + z , LCA(a,y) + LCA(b,x) + z}) << "\n";
  91.   }
  92. }
  93.  
  94. int main(){
  95.   ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
  96.   int tt=1,var=0;
  97.   cin >> tt;
  98.   while(tt--)
  99.   {
  100.     solve();
  101.   }
  102.   return 0;
  103. }
Success #stdin #stdout 0.01s 7072KB
comments (?)
stdin
copy 
1
6 3
1 2 2
1 3 4
2 6 3
3 4 1
3 5 10
3 6 6
1 4
2 5
3 2
stdout
copy 
5
16
6
https://ideone.com/xF50ig
language:
C++14 (gcc 8.3)
created:
327 days ago
visibility:
secret

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!