fork(2) download
copy 
  1. # include <algorithm>
  2. # include <iostream>
  3. # include <queue>
  4. # include <vector>
  5. using namespace std;
  6.  
  7. using ll = long long;
  8. using pii = pair<int, int>;
  9.  
  10. vector<pii> v[252020];
  11. ll ans = 0;
  12. template<class T>
  13. struct MergeSet {
  14.     priority_queue<T, std::vector<T>, std::greater<T>> s;
  15.     T shift;
  16.     void update(T val) {
  17.         shift = shift + val;
  18.     }
  19.     T popFront() {
  20.         auto elem = s.top();
  21.         s.pop();
  22.         return elem + shift;
  23.     }
  24.     T front() {
  25.         auto elem = s.top();
  26.         return elem + shift;
  27.     }
  28.     void insert(T elem) {
  29.         s.push(elem - shift);
  30.     }
  31.     void clear() {
  32.         s.clear();
  33.         shift = T{};
  34.     }
  35. };
  36. template<class T>
  37. void merge(MergeSet<T>& a, MergeSet<T>& b) {
  38.     if (a.s.size() < b.s.size()) {
  39.         swap(a, b);
  40.     }
  41.     while (!b.s.empty()) {
  42.         auto elem = b.s.top();
  43.         b.s.pop();
  44.         a.insert(elem + b.shift);
  45.     }
  46. }
  47.  
  48. ll need[250202];
  49. MergeSet<ll> have[250202];
  50. MergeSet<ll> matched[250202];
  51. int cnt[250202];
  52. void go(int cur, int p = -1) {
  53.     if (cnt[cur] < 0) {
  54.         need[cur] = -cnt[cur];
  55.     } else {
  56.         for (int i = 0; i < cnt[cur]; ++i) {
  57.             have[cur].insert(0);
  58.         }
  59.     }
  60.     for (pii e : v[cur]) {
  61.         int to = e.first;
  62.         if (to == p) continue;
  63.         go(to, cur);
  64.         int len = e.second;
  65.         ans += need[to] * 1LL * len;
  66.         have[to].update(len);
  67.         matched[to].update(len);
  68.         merge(have[cur], have[to]);
  69.         merge(matched[cur], matched[to]);
  70.         need[cur] += need[to];
  71.     }
  72.     while (have[cur].s.size() > 0 && need[cur] > 0) {
  73.         ll a = have[cur].popFront();
  74.         ans += a;
  75.         matched[cur].insert(-a);
  76.         need[cur]--;
  77.     }
  78.     while (have[cur].s.size() > 0 && matched[cur].s.size() > 0) {
  79.         auto a = have[cur].front();
  80.         auto b = matched[cur].front();
  81.         if (a + b < 0) {
  82.             ans += a + b;
  83.             have[cur].popFront();
  84.             matched[cur].popFront();
  85.             have[cur].insert(-b);
  86.             matched[cur].insert(-a);
  87.         } else {
  88.             break;
  89.         }
  90.     }
  91. }
  92.  
  93. int main() {
  94.     ios_base::sync_with_stdio(0);cin.tie(0);
  95.     int n;
  96.     cin >> n;
  97.     for (int i = 0; i < n - 1; ++i) {
  98.         int x, y, w;
  99.         cin >> x >> y >> w;
  100.         --x; --y;
  101.         v[x].push_back({y, w});
  102.         v[y].push_back({x, w});
  103.     }
  104.     for (int i = 0; i < n; ++i) {
  105.         int x, y;
  106.         cin >> x >> y;
  107.         cnt[i] = x - y;
  108.     }
  109.     go(0);
  110.     cout << ans << endl;
  111.     return 0;
  112. }
  113.  
  114.  
  115.  
Success #stdin #stdout 0.01s 28612KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4NOAx0
language:
C++ (gcc 8.3)
created:
6 years 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!