#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = (int)2e5 + 5;
struct PersistentLiChaoTree{
struct line{
ll m, b;
line(){ m = b = 1e9;}
line(ll _m, ll _b){ m = _m, b = _b; }
ll eval(ll x){ return m * x + b; }
};
struct node{
node * l, * r;
line L;
node(){ l = 0, r = 0, L = line(); }
node(node * _l, node * _r, line _L){
l = _l, r = _r, L = _L;
}
};
node * add_line(node * u, int l, int r, line L){
node * v = new node(u->l, u->r, u->L);
int m = (l + r)>>1;
bool lef = L.eval(l) < v->L.eval(l);
bool mid = L.eval(m) < v->L.eval(m);
if(mid)
swap(v->L, L);
if(r - l == 1)
return v;
if(lef != mid) {
if(! v->l)
v->l = new node(0, 0, L);
v->l = add_line(v->l, l, m, L);
}
else{
if(! v->r)
v->r = new node(0, 0, L);
v->r = add_line(v->r, m, r, L);
}
return v;
}
ll get(node * u, int l, int r, int x) {
int m = (l + r) / 2;
if(r - l == 1)
return u->L.eval(x);
if(x < m){
ll q2 = (u->l) ? get(u->l, l, m, x) : LLONG_MAX;
return min(q2, u->L.eval(x));
}
ll q2 = (u->r) ? get(u->r, m, r, x) : LLONG_MAX;
return min(q2, u->L.eval(x));
}
vector<node*> roots;
PersistentLiChaoTree(){
node * u = new node(0, 0, line());
roots.push_back(u);
}
int update(int old, line l){
roots.push_back(add_line(roots[old], 0, 1e9, l));
return (int)roots.size() - 1;
}
ll query(int id, ll x){
return get(roots[id], 0, 1e9, x);
}
} lt;
vector<pair<int,int>> G[maxn];
ll speed[maxn], start[maxn], dp[maxn], sumW[maxn];
int n, par[maxn];
int pos[maxn];
void dfs(int u){
pos[u] = lt.update(pos[par[u]], PersistentLiChaoTree::line(-sumW[u], dp[u]));
for(auto [v, w]:G[u]){
if(v == par[u])
continue;
sumW[v] = sumW[u] + w;
par[v] = u;
dp[v] = sumW[v] * speed[v] + start[v] + lt.query(pos[u], speed[v]);
dfs(v);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
int u, v, w;
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
for(int i = 2; i <= n; i++)
cin >> start[i] >> speed[i];
dfs(1);
for(int i = 2; i <= n; i++)
cout << dp[i] << ' ';
cout << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5196 KB |
Output is correct |
2 |
Correct |
10 ms |
9204 KB |
Output is correct |
3 |
Runtime error |
111 ms |
65540 KB |
Execution killed with signal 9 |
4 |
Runtime error |
127 ms |
65540 KB |
Execution killed with signal 9 |
5 |
Runtime error |
132 ms |
65540 KB |
Execution killed with signal 9 |
6 |
Runtime error |
158 ms |
65540 KB |
Execution killed with signal 9 |
7 |
Runtime error |
140 ms |
65540 KB |
Execution killed with signal 9 |
8 |
Runtime error |
152 ms |
65540 KB |
Execution killed with signal 9 |
9 |
Runtime error |
143 ms |
65540 KB |
Execution killed with signal 9 |
10 |
Runtime error |
136 ms |
65540 KB |
Execution killed with signal 9 |