#include <bits/stdc++.h>
using namespace std;
template <typename T>
int bins(int l, int r, T f) {
while (l < r) {
int m = (l + r) / 2;
f(m) ? r = m : l = m + 1;
}
return l;
}
const long INF = 1e18;
int n, s[100100], t[100100];
long dp[100100];
vector<pair<int, int>> g[100100];
struct Line {
long m, c;
long operator()(long x) { return m * x + c; }
} cht[100100];
long intersect(Line a, Line b) {
long num = b.c - a.c, dem = a.m - b.m;
return num / dem - ((num ^ dem) < 0 && num % dem);
}
void dfs(int u, int p, int ed, long cd) {
if (u != 1) {
dp[u] = cd * t[u] + s[u] - cht[bins(0, ed - 1, [&](int m) {
return cht[m](t[u]) > cht[m + 1](t[u]);
})](t[u]);
Line l{cd, -dp[u]};
int ned = bins(0, ed - 1, [&](int m) {
return intersect(cht[m], cht[m + 1]) >= intersect(cht[m + 1], l);
}) + 1;
swap(cht[ned], l);
for (auto [v, d] : g[u]) {
if (v == p) continue;
dfs(v, u, ned + 1, cd + d);
}
swap(cht[ned], l);
} else {
for (auto [v, d] : g[u]) {
if (v == p) continue;
dfs(v, u, ed, cd + d);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1, u, v, d; i <= n - 1; ++i) {
scanf("%d %d %d", &u, &v, &d);
g[u].emplace_back(v, d);
g[v].emplace_back(u, d);
}
for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
dfs(1, -1, 1, 0);
for (int i = 2; i <= n; ++i) printf("%ld%c", dp[i], i == n ? '\n' : ' ');
}
// f_j(x) := -dp[j] + dep[j] * x
// dp[j] + (d - x) t_i + s_i
// = dp[j] - x * t_i + d * t_i + s_i
// = -f_j(t_i) + d * t_i + s_i
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
46 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
harbingers.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
48 | scanf("%d %d %d", &u, &v, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:52:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
52 | for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2636 KB |
Output is correct |
| 2 |
Correct |
4 ms |
3020 KB |
Output is correct |
| 3 |
Correct |
55 ms |
8908 KB |
Output is correct |
| 4 |
Correct |
83 ms |
12116 KB |
Output is correct |
| 5 |
Correct |
99 ms |
14632 KB |
Output is correct |
| 6 |
Correct |
114 ms |
17500 KB |
Output is correct |
| 7 |
Correct |
66 ms |
9112 KB |
Output is correct |
| 8 |
Correct |
135 ms |
13168 KB |
Output is correct |
| 9 |
Correct |
149 ms |
15428 KB |
Output is correct |
| 10 |
Correct |
127 ms |
14284 KB |
Output is correct |
