fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int maxN = 2e5 + 5;
  5. //
  6. int N, A, B;
  7. int h[maxN], up[20][maxN];
  8. int vertex[maxN], edge[maxN];
  9. long long ans, C1[maxN], C2[maxN];
  10. vector<pair<int, int>> adj[maxN];
  11. //
  12. void DFS_1 (int u = 1)
  13. {
  14.     for (auto [id, v] : adj[u])
  15.     {
  16.         if (v == up[0][u])
  17.             continue;
  18.         h[v] = h[u] + 1;
  19.         up[0][v] = u;
  20.         for (int i = 1; i < 20; ++i)
  21.             up[i][v] = up[i - 1][up[i - 1][v]];
  22.         DFS_1(v);
  23.     }
  24. }
  25. int LCA (int u, int v)
  26. {
  27.     if (h[u] != h[v])
  28.     {
  29.         if (h[u] < h[v])
  30.             swap(u, v);
  31.         for (int k = h[u] - h[v], i = 0; (1 << i) <= k; ++i)
  32.             if (k >> i & 1)
  33.                 u = up[i][u];
  34.     }
  35.     if (u == v)
  36.         return u;
  37.     for (int i = __lg(h[v]); i >= 0; --i)
  38.         if (up[i][u] != up[i][v])
  39.             u = up[i][u],
  40.             v = up[i][v];
  41.     return up[0][v];
  42. }
  43. void DFS_2 (int u = 1)
  44. {
  45.     int index = 0;
  46.     //
  47.     for (auto [id, v] : adj[u])
  48.         if (v == up[0][u])
  49.             index = id;
  50.         else
  51.             DFS_2(v),
  52.             vertex[u] += vertex[v];
  53.     edge[index] = vertex[u];
  54. }
  55. //
  56. void process (void)
  57. {
  58.     cin >> N;
  59.     for (int i = 1; i < N; ++i)
  60.     {
  61.         cin >> A >> B >> C1[i] >> C2[i];
  62.         adj[A].emplace_back(i, B);
  63.         adj[B].emplace_back(i, A);
  64.     }
  65.  
  66.     DFS_1();
  67.     for (int i = 1; i < N; ++i)
  68.     {
  69.         ++vertex[i];
  70.         ++vertex[i + 1];
  71.         vertex[LCA(i, i + 1)] -= 2;
  72.     }
  73.     DFS_2();
  74.     for (int i = 1; i < N; ++i)
  75.         ans += min(C1[i] * edge[i], C2[i]);
  76.  
  77.     cout << ans;
  78. }
  79. //
  80. signed main (void)
  81. {
  82.     ios_base::sync_with_stdio(false);
  83.     cin.tie(nullptr), cout.tie(nullptr);
  84.     process();
  85. }
  86.  
Success #stdin #stdout 0.01s 11480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/l8i5IA
https://o...content-available-to-author-only...i.info/problem/coci1920_r5_putovanje
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!