fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int maxN = 1005;
  5. //
  6. int N, Q, d[maxN], h[maxN], up[maxN][20];
  7. vector<pair<int, int>> edge[maxN];
  8. //
  9. void DFS (int u)
  10. {
  11.     int v, l;
  12.     //
  13.     for (pair<int, int> p : edge[u])
  14.     {
  15.         v = p.first, l = p.second;
  16.         if (v == up[u][0])
  17.             continue;
  18.         d[v] = d[u] + l;
  19.         h[v] = h[u] + 1;
  20.         up[v][0] = u;
  21.         for (int i = 1; i < 20; ++i)
  22.             up[v][i] = up[up[v][i - 1]][i - 1];
  23.         DFS(v);
  24.     }
  25. }
  26. int LCA (int u, int v)
  27. {
  28.     if (h[u] != h[v])
  29.     {
  30.         if (h[u] < h[v])
  31.             swap(u, v);
  32.         for (int k = h[u] - h[v], i = 0; (1 << i) <= k; ++i)
  33.             if (k >> i & 1)
  34.                 u = up[u][i];
  35.     }
  36.     if (u == v)
  37.         return u;
  38.     for (int i = __lg(h[v]); i >= 0; --i)
  39.         if (up[u][i] != up[v][i])
  40.             u = up[u][i], v = up[v][i];
  41.     return up[v][0];
  42. }
  43. //
  44. void process (void)
  45. {
  46.     int A, B, L;
  47.     //
  48.     cin >> N >> Q;
  49.     for (int i = 1; i < N; ++i)
  50.         cin >> A >> B >> L,
  51.         edge[A].emplace_back(B, L),
  52.         edge[B].emplace_back(A, L);
  53.  
  54.     DFS(1);
  55.  
  56.     while (Q--)
  57.         cin >> A >> B,
  58.         cout << d[A] + d[B] - d[LCA(A, B)] * 2 << '\n';
  59. }
  60. //
  61. signed main (void)
  62. {
  63.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  64.     process();
  65. }
  66.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/3TPMTs
https://o...content-available-to-author-only...i.info/problem/pwalk
language:
C++14 (gcc 8.3)
created:
4 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!