#include <bits/stdc++.h>
using namespace std;
const int N = 100'000 + 10;
int n;
vector<pair<int, int>> ad[N];
int s[N], velocity[N];
int sz[N], d[N];
void dfs(int u, int p = -1) {
for (const auto& [v , w] : ad[u]) {
if (v == p) continue;
d[v] = d[u] + w;
dfs(v, u);
sz[u] += sz[v] + 1;
}
}
int head[N], par[N];
void hld(int u, int p = -1) {
sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) {
return sz[a.first] > sz[b.first];
});
bool heavy = false;
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
par[v] = u;
if (!heavy) head[v] = head[u], heavy = true, hld(v, u);
else head[v] = v, hld(v, u);
}
}
vector<int> get(int u) {
vector<int> ret;
while (head[u] != 1) {
ret.push_back(head[u]);
u = par[head[u]];
}
ret.push_back(1);
return ret;
}
struct Line {
long long a, b;
double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
};
struct CHT {
vector<Line> hull;
vector<tuple<int, Line>> save;
void add(Line line) {
while (hull.size() > 1 && hull.end()[-2].x(hull.end()[-1]) >= hull.end()[-2].x(line)) {
save.emplace_back(1, hull.end()[-1]);
hull.pop_back();
}
save.emplace_back(-1, line);
hull.push_back(line);
}
long long query(int u) {
auto cal = [&](int it) {
return hull[it].a * velocity[u] + hull[it].b + 1ll * d[u] * velocity[u] + s[u];
};
int l = 0, r = hull.size() - 2, it = 0;
while (l <= r) {
int mid = l + r >> 1;
if (cal(mid) >= cal(mid + 1)) l = it = mid + 1;
else r = mid - 1;
}
return cal(it);
}
} convex[N];
long long dp[N];
void dfs1(int u, int p = 0) {
auto& ret = dp[u];
for (const auto& x : get(u)) ret = min(ret, convex[x].query(u));
convex[head[u]].add({-d[u], ret});
assert(ret <= INT32_MAX);
sort(ad[u].begin(), ad[u].end(), [&](const auto& a, const auto& b) {
return sz[a.first] < sz[b.first];
});
for (const auto& [v, w] : ad[u]) {
if (v == p) continue;
dfs1(v, u);
}
bool pass = false;
while (convex[head[u]].save.size()) {
const auto& [t, line] = convex[head[u]].save.end()[-1];
if (t == -1) {
if (pass) break;
convex[head[u]].hull.pop_back();
pass = true;
} else convex[head[u]].hull.push_back(line);
convex[head[u]].save.pop_back();
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 2; i <= n; ++i) {
int u, v, w; cin >> u >> v >> w;
ad[u].push_back({v, w});
ad[v].push_back({u, w});
}
for (int i = 2; i <= n; ++i) cin >> s[i] >> velocity[i];
dfs(1); hld(head[1] = par[1] = 1);
for (int i = 1; i <= n; ++i) if (head[i] == i) convex[i].hull.push_back({0, 0});
memset(dp, 40, sizeof dp);
dfs1(1);
for (int i = 2; i <= n; ++i) cout << dp[i] << " \n"[i == n];
}
Compilation message
harbingers.cpp:46:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
46 | double x(const auto& rhs) { return 1.0 * (rhs.b - b) / (a - rhs.a); }
| ^~~~
harbingers.cpp: In member function 'long long int CHT::query(int)':
harbingers.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
66 | int mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
4 ms |
11292 KB |
Output is correct |
| 3 |
Runtime error |
40 ms |
29944 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
59 ms |
34644 KB |
Execution killed with signal 6 |
| 5 |
Correct |
73 ms |
31508 KB |
Output is correct |
| 6 |
Runtime error |
101 ms |
35004 KB |
Memory limit exceeded |
| 7 |
Correct |
52 ms |
21752 KB |
Output is correct |
| 8 |
Runtime error |
85 ms |
35604 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
69 ms |
40244 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
61 ms |
39436 KB |
Execution killed with signal 6 |
