#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
typedef long double ld;
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
ll dep[MAXN];
ll val[MAXN], start[MAXN], dp[MAXN];
void calc (int pos, int par) {
for (auto j : adj[pos]) {
if (j.first == par) continue;
dep[j.first] = j.second + dep[pos];
calc(j.first, pos);
}
}
pair <ll, ll> hull[MAXN];
ld inter (pair <ll, ll> a, pair <ll, ll> b) {
return 1.0 * (a.second - b.second) / (b.first - a.first);
}
int sze = 0;
ll get (ll x) {
if (sze == 1) {
return hull[0].first * x + hull[0].second;
}
if (inter(hull[sze - 1], hull[sze - 2]) + 1e-9 < x) {
return hull[sze - 1].first * x + hull[sze - 1].second;
}
int l = 0, r = sze - 2, ans = sze - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (inter(hull[mid], hull[mid + 1]) > x + 1e-9) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
return hull[ans].first * x + hull[ans].second;
}
void dfs (int pos, int par) {
int prev_sze = sze;
if (par != -1) dp[pos] = start[pos] + dep[pos] * val[pos] + get(val[pos]);
pair <ll, ll> line = {-dep[pos], dp[pos]};
int l = 1, r = sze - 1, ans = sze;
while (l <= r) {
int mid = (l + r) >> 1;
if (inter(hull[mid], hull[mid - 1]) > inter(line, hull[mid]) + 1e-9) {
r = mid - 1; ans = mid;
} else {
l = mid + 1;
}
}
sze = ans + 1; pair <ll, ll> pp = hull[sze - 1]; hull[sze - 1] = line;
for (auto j : adj[pos]) if (j.first != par) dfs(j.first, pos);
hull[sze - 1] = pp; sze = prev_sze;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int a, b, c;
cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
for (int i = 2; i <= n; i++) cin >> start[i] >> val[i];
calc(1, -1);
dfs(1, -1);
for (int i = 2; i <= n; i++) cout << dp[i] << " ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
5212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5468 KB |
Output is correct |
| 3 |
Correct |
28 ms |
12120 KB |
Output is correct |
| 4 |
Correct |
41 ms |
14932 KB |
Output is correct |
| 5 |
Correct |
48 ms |
17492 KB |
Output is correct |
| 6 |
Correct |
62 ms |
20116 KB |
Output is correct |
| 7 |
Correct |
37 ms |
12628 KB |
Output is correct |
| 8 |
Correct |
72 ms |
16588 KB |
Output is correct |
| 9 |
Correct |
82 ms |
18516 KB |
Output is correct |
| 10 |
Correct |
67 ms |
17396 KB |
Output is correct |
