fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  3. #define FOD(i, a, b) for(int i = a; i >= b; i--)
  4. #define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
  5. #define fi first
  6. #define se second
  7. #define maxn int(2e5 + 5)
  8. #define logn 20
  9.  
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13. typedef pair<int, int> pii;
  14.  
  15. int n, q, h[maxn], up[maxn][logn];
  16.  
  17. ll f[maxn];
  18.  
  19. vector<pii> adj[maxn];
  20.  
  21. void dfs(int u) {
  22.     for(pii x : adj[u]) {
  23.         int v = x.fi, w = x.se;
  24.         if(v == up[u][0]) continue;
  25.         h[v] = h[u] + 1;
  26.         f[v] = f[u] + w;
  27.         up[v][0] = u;
  28.         FOR(i, 1, logn - 1)
  29.             up[v][i] = up[up[v][i - 1]][i - 1];
  30.         dfs(v);
  31.     }
  32. }
  33.  
  34. int lca(int u, int v) {
  35.     if(h[u] < h[v]) swap(u, v);
  36.     int k = h[u] - h[v];
  37.     FOD(i, logn - 1, 0)
  38.         if(k >> i & 1) u = up[u][i];
  39.     if(u == v) return u;
  40.     FOD(i, logn - 1, 0)
  41.         if(up[u][i] != up[v][i])
  42.             u = up[u][i], v = up[v][i];
  43.     return up[u][0];
  44. }
  45.  
  46. ll dist(int u, int v) {
  47.     return f[u] + f[v] - 2 * f[lca(u, v)];
  48. }
  49.  
  50. int main()
  51. {
  52.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  53.     cin >> n;
  54.     FOR(i, 1, n - 1) {
  55.         int u, v, w;
  56.         cin >> u >> v >> w;
  57.         adj[u].push_back({ v, w });
  58.         adj[v].push_back({ u, w });
  59.     }
  60.     cin >> q;
  61.     dfs(1);
  62.     while (q--) {
  63.         int a, b, c;
  64.         cin >> a >> b >> c;
  65.         int ab = lca(a, b);
  66.         int ac = lca(a, c);
  67.         int bc = lca(b, c);
  68.         ll S1 = dist(a, ab) + dist(b, ab) + dist(c, ab);
  69.         ll S2 = dist(a, ac) + dist(b, ac) + dist(c, ac);
  70.         ll S3 = dist(b, bc) + dist(c, bc) + dist(a, bc);
  71.         cout << min({ S1, S2, S3 }) << '\n';  
  72.     }
  73.     return 0;
  74. }
Success #stdin #stdout 0.01s 10168KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8A8yd5
language:
C++14 (gcc 8.3)
created:
1 day 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!