fork(2) download
  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
stdin
Standard input is empty
stdout
0