#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct Line {
ll m, c;
ll operator()(ll x) { return m * x + c; }
} cht[100001];
int ptr = 0;
double intersect(Line A, Line B) {
return double(B.c - A.c) / (A.m - B.m);
}
ll dp[100001], s[100001], v[100001], to_root[100001];
vector<pair<int, int>> graph[100001];
void dfs(int node, int parent = 1) {
int l = 0, r = ptr;
while (l != r) {
int mid = (l + r) / 2;
if (intersect(cht[mid], cht[mid + 1]) >= v[node]) r = mid;
else l = mid + 1;
}
dp[node] = s[node] + v[node] * to_root[node] + cht[l](v[node]);
Line curr = {-to_root[node], dp[node]};
l = 0, r = ptr;
while (l != r) {
int mid = (l + r) / 2;
if (intersect(cht[mid], cht[mid + 1]) >= intersect(cht[mid], curr)) r = mid;
else l = mid + 1;
}
int prev_ptr = ptr;
Line replaced = cht[l + 1];
cht[l + 1] = curr;
ptr = l + 1;
for (pair<int, int> i : graph[node]) if (i.first != parent) {
to_root[i.first] = to_root[node] + i.second;
dfs(i.first, node);
}
cht[ptr] = replaced;
ptr = prev_ptr;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int u, v, d;
cin >> u >> v >> d;
graph[u].push_back({v, d});
graph[v].push_back({u, d});
}
for (int i = 2; i <= n; i++) cin >> s[i] >> v[i];
for (pair<int, int> i : graph[1]) {
to_root[i.first] = i.second;
dfs(i.first);
}
for (int i = 2; i <= n; i++) cout << dp[i] << " \n"[i == n];
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2688 KB |
Output is correct |
2 |
Correct |
4 ms |
3200 KB |
Output is correct |
3 |
Correct |
47 ms |
10360 KB |
Output is correct |
4 |
Correct |
84 ms |
13944 KB |
Output is correct |
5 |
Correct |
106 ms |
17016 KB |
Output is correct |
6 |
Correct |
115 ms |
20088 KB |
Output is correct |
7 |
Correct |
62 ms |
11768 KB |
Output is correct |
8 |
Correct |
127 ms |
16760 KB |
Output is correct |
9 |
Correct |
126 ms |
18552 KB |
Output is correct |
10 |
Correct |
114 ms |
17396 KB |
Output is correct |