#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'
const int LIM = 1e9, INF = 2e9;
struct Line {
int m, c;
Line(int M = 0, int C = INF) : m(M), c(C) {}
int operator()(int x) {
return m * x + c;
}
};
struct LiChaoTree {
Line v;
LiChaoTree *L = NULL, *R = NULL;
void insert(Line u, auto &rb, int l = 0, int r = LIM + 1) {
int m = (l + r) / 2;
if(u(m) < v(m)) {
rb.emplace_back(&v, v);
swap(u, v);
}
if(r - l < 2) return;
u.m > v.m ? (L ? : L = new LiChaoTree)->insert(u, rb, l, m):
(R ? : R = new LiChaoTree)->insert(u, rb, m, r);
}
int query(int x, int l = 0, int r = LIM + 1) {
if(r - l < 2) return v(x);
int m = (l + r) / 2;
return min(v(x), x < m ? (L ? L->query(x, l, m) : INF) : (R ? R->query(x, m, r) : INF));
}
} lt;
const int Z = 1e5+1;
int N, S[Z], V[Z], dp[Z];
vector<array<int, 2>> g[Z];
void dfs(int u, int p, int d) {
vector<pair<Line*, Line>> rb;
dp[u] = u ? lt.query(V[u]) + S[u] + V[u] * d : int();
lt.insert(Line(-d, dp[u]), rb);
// cout <<
// cerr << u sp p sp d sp size(g[u]) nl;
// cerr << u sp p sp d nl;
for(auto &[v, w] : g[u]) if(v != p) {
// cerr << u sp v sp d sp w nl;
dfs(v, u, d + w);
}
for(int i = size(rb); i--; )
(*rb[i].first) = rb[i].second;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for(int i = 1; i < N; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 1; i < N; ++i)
cin >> S[i] >> V[i];
dfs(0, 0, 0);
for(int i = 1; i < N; ++i)
cout << dp[i] << ' ';
}
Compilation message
harbingers.cpp:20:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
20 | void insert(Line u, auto &rb, int l = 0, int r = LIM + 1) {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
2 |
Correct |
5 ms |
5196 KB |
Output is correct |
3 |
Runtime error |
81 ms |
50300 KB |
Memory limit exceeded |
4 |
Runtime error |
113 ms |
65536 KB |
Memory limit exceeded |
5 |
Runtime error |
124 ms |
65540 KB |
Execution killed with signal 9 |
6 |
Runtime error |
135 ms |
65540 KB |
Execution killed with signal 9 |
7 |
Runtime error |
103 ms |
34628 KB |
Memory limit exceeded |
8 |
Runtime error |
184 ms |
58348 KB |
Memory limit exceeded |
9 |
Runtime error |
122 ms |
65540 KB |
Execution killed with signal 9 |
10 |
Runtime error |
153 ms |
65544 KB |
Execution killed with signal 9 |