fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define int long long
  5. #define cint const int
  6. #define left(id) (id << 1)
  7. #define right(id) (id << 1 | 1)
  8. #define mid(a, b) ((a + b) >> 1)
  9.  
  10. const int MAXN     = 2e5 + 15;
  11. const int oo       = 1e9;
  12. const int MOD      = 1e9 + 7;
  13. const int LOG      = 20;
  14.  
  15. int N;
  16. int pre[MAXN], h[MAXN], par[MAXN];
  17. map<pair<int, int>, int> t1, t2;
  18. vector<int> g[MAXN];
  19. int f[MAXN][LOG + 2];
  20.  
  21. void S() {
  22.     for (int i = 1; i <= N; i++) f[i][0] = par[i];
  23.     for (int j = 1; j <= 20; j++) {
  24.         for (int i = 1; i <= N; i++) {
  25.             f[i][j] = f[f[i][j - 1]][j - 1];
  26.         }
  27.     }
  28. }
  29.  
  30. int LCA(int u, int v) {
  31.     if (h[u] < h[v]) swap(u, v);
  32.     int diff = h[u] - h[v];
  33.     for (int log = 20; log >= 0; log--) {
  34.         if (diff - (1 << log) < 0) continue;
  35.         else {
  36.             diff -= (1 << log);
  37.             u = f[u][log];
  38.         }
  39.     }
  40.     if (u == v) return u;
  41.     for (int log = 20; log >= 0; log--) {
  42.         if (f[u][log] != f[v][log]) {
  43.             u = f[u][log];
  44.             v = f[v][log];
  45.         }
  46.     }
  47.     return par[u];
  48. }
  49.  
  50. void DFS(int u, int p) {
  51.     par[u] = p;
  52.     h[u] = h[p] + 1;
  53.     for (auto v : g[u]) {
  54.         if (v == p) continue;
  55.         DFS(v, u);
  56.     }
  57. }
  58.  
  59. void DFS1(int u, int p) {
  60.     for (auto v : g[u]) {
  61.         if (v == p) continue;
  62.         pre[u] += pre[v];
  63.         DFS1(v, u);
  64.     }
  65. }
  66.  
  67.  
  68. main() {
  69.     ios_base::sync_with_stdio(0);
  70.     cin.tie(0);
  71.  
  72.     freopen("travel.inp", "r", stdin);
  73.     freopen("travel.out", "w", stdout);
  74.  
  75.     cin >> N;
  76.     for (int i = 1; i < N; i++) {
  77.         int u, v, a, b;
  78.         cin >> u >> v >> a >> b;
  79.         g[u].pb(v);
  80.         g[v].pb(u);
  81.         t1[{u, v}] = t1[{v, u}] = a;
  82.         t2[{u, v}] = t2[{v, u}] = b;
  83.     }
  84.  
  85.     DFS(1, 0);
  86.     S();
  87.  
  88.     for (int i = 1; i < N; i++) {
  89.         int lca = LCA(i, i + 1);
  90.         pre[i]++;
  91.         pre[i + 1]++;
  92.         pre[lca] -= 2;
  93.     }
  94.     DFS1(1, 0);
  95.     int ans = 0;
  96.     for (int i = 1; i <= N; i++) {
  97.         if (par[i] == 0) continue;
  98.         if (t2[{i, par[i]}] < t1[{i, par[i]}] * pre[i]) ans += t2[{i, par[i]}];
  99.         else ans += t1[{i, par[i]}] * pre[i];
  100.     }
  101.  
  102.     cout << ans;
  103. }
  104.  
Success #stdin #stdout 0.01s 11984KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pJsIsJ
language:
C++14 (gcc 8.3)
created:
8 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!