#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+10, oo = 4e18;
vector<pair<int, int>> edges[N];
ll p[N], s[N], v[N], sum[N], dp[N], n;
void mini(ll &x, ll y) {
if(x > y) {
x = y;
}
}
struct line {
int k, b;
line(int _k, int _b) : k(_k), b(_b) {}
line() : line(-1, -1) {}
ll f(int x) {
if(k == -1 && b == -1) return 4e18;
return (ll)k*x + b;
}
};
struct node {
node *L, *R;
line l;
node() : L(NULL), R(NULL), l() {}
} *root;
pair<line*, line> ops[1000005];
int timer = 0;
void add_line(ll l, ll r, line ln, node *&t) {
if(t == NULL) t = new node();
ll m = l + r >> 1;
bool lft = t->l.f(l) < ln.f(l);
bool mid = t->l.f(m) < ln.f(m);
if(lft == mid && !lft) {
line save = t->l;
pair<line*, line> p = {&(t->l), save};
swap(ln, t->l);
if(timer <= 1e6)ops[++timer] = p;
}
if(lft != mid && !mid) {
line save = t->l;
pair<line*, line> p = {&(t->l), save};
swap(ln, t->l);
if(timer <= 1e6)ops[++timer] = p;
}
if(l == r) {
return;
}
if(lft == mid) {
add_line(m+1, r, ln, t->R);
} else {
add_line(l, m, ln, t->L);
}
}
ll get_min(ll l, ll r, ll x, node *&t) {
if(t == NULL || l > x || r < x) return oo;
if(l == r) return t->l.f(x);
ll m = l + r >> 1;
ll children = min(get_min(l, m, x, t->L), get_min(m+1, r, x, t->R));
ll all = min(children, t->l.f(x));
return all;
}
void rollback(int T) {
while(timer > T) {
pair<line*, line> p = ops[timer--];
(*p.first) = p.second;
}
}
void dfs(int x, int p) {
int T = timer;
if(x == 1) {
dp[x] = 0;
} else {
dp[x] = get_min(1, 1e9, v[x], root) + sum[x] * v[x] + s[x];
}
add_line(1, 1e9, line(-sum[x], dp[x]), root);
for(pair<int, int> to : edges[x]) {
if(to.first != p) {
sum[to.first] = sum[x] + to.second;
dfs(to.first, x);
}
}
rollback(T);
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 0; i < n-1; ++i) {
int u, v, w; cin >> u >> v >> w;
edges[u].push_back({v, w});
edges[v].push_back({u, w});
}
for(int i = 2; i <= n; ++i) {
cin >> s[i] >> v[i];
}
dfs(1, 0);
for(int i = 2; i <= n; ++i) {
cout << dp[i] << ' ';
}
}
Compilation message
harbingers.cpp: In function 'void add_line(long long int, long long int, line, node*&)':
harbingers.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | ll m = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'long long int get_min(long long int, long long int, long long int, node*&)':
harbingers.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | ll m = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20684 KB |
Output is correct |
| 2 |
Correct |
15 ms |
21068 KB |
Output is correct |
| 3 |
Incorrect |
74 ms |
26764 KB |
Output isn't correct |
| 4 |
Incorrect |
114 ms |
30460 KB |
Output isn't correct |
| 5 |
Runtime error |
134 ms |
32788 KB |
Memory limit exceeded |
| 6 |
Runtime error |
184 ms |
35504 KB |
Memory limit exceeded |
| 7 |
Correct |
128 ms |
27828 KB |
Output is correct |
| 8 |
Incorrect |
179 ms |
31792 KB |
Output isn't correct |
| 9 |
Runtime error |
188 ms |
34308 KB |
Memory limit exceeded |
| 10 |
Runtime error |
163 ms |
36024 KB |
Memory limit exceeded |
