#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
struct Line {
ll k, m;
};
ll intersect_x(const Line &l1, const Line &l2) {
ll a = l1.m - l2.m, b = l2.k - l1.k;
return a / b + ((a ^ b) > 0 && a % b);
}
ll get_y(const Line &l, ll x) {
return l.k * x + l.m;
}
const int N = 100005;
vector<pair<int, int>> g[N];
ll prep[N], vel[N], dp[N];
pair<Line, ll> hull[N];
void compute_dp(int u, int p = 0, ll total_d = 0, int hull_n = 0) {
if (u != 1) {
int l = 0, r = hull_n;
while (r - l > 1) {
int m = (l + r) / 2;
if (hull[m].second <= vel[u]) {
l = m;
} else {
r = m;
}
}
dp[u] = get_y(hull[l].first, vel[u]) + total_d * vel[u] + prep[u];
}
Line next_line = {-total_d, dp[u]};
int l = 0, r = hull_n;
while (r - l > 1) {
int m = (l + r) / 2;
if (hull[m].second < intersect_x(hull[m].first, next_line)) {
l = m;
} else {
r = m;
}
}
auto last = hull[r];
ll next_x = r == 0 ? LLONG_MIN : intersect_x(hull[r - 1].first, next_line);
hull[r] = {next_line, next_x};
for (auto [v, d] : g[u]) {
if (v == p) {
continue;
}
compute_dp(v, u, total_d + d, r + 1);
}
hull[r] = last;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.setf(cout.fixed);
cout.precision(20);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, d;
cin >> u >> v >> d;
g[u].emplace_back(v, d);
g[v].emplace_back(u, d);
}
for (int i = 2; i <= n; i++) {
cin >> prep[i] >> vel[i];
}
compute_dp(1);
for (int i = 2; i <= n; i++) {
cout << dp[i] << " ";
}
cout << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2668 KB |
Output is correct |
2 |
Correct |
4 ms |
3180 KB |
Output is correct |
3 |
Correct |
59 ms |
12004 KB |
Output is correct |
4 |
Correct |
83 ms |
16228 KB |
Output is correct |
5 |
Correct |
101 ms |
20068 KB |
Output is correct |
6 |
Correct |
133 ms |
24036 KB |
Output is correct |
7 |
Correct |
65 ms |
12516 KB |
Output is correct |
8 |
Correct |
150 ms |
18236 KB |
Output is correct |
9 |
Correct |
143 ms |
20888 KB |
Output is correct |
10 |
Correct |
126 ms |
19296 KB |
Output is correct |