#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define all(x) begin(x), end(x)
#define pb push_back
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int mxn = 2e5+5;
const ll inf = 1e18;
const ld eps = 1e-13;
mt19937 _rand(time(0));
struct line{
ll m, b;
bool isq;
ll x;
ll eval(ll X) const{
return X * m + b;
}
ll intersect(const line &l) const{
return (l.b - b) / (m - l.m);
}
bool operator < (const line &l) const{
if(l.isq) return x < l.x;
else return m > l.m;
}
};
set<line> hull;
set<line> hull2[mxn];
typedef set<line>::iterator iter;
bool cPrev(iter it){
return it != hull.begin();
}
bool cNext(iter it){
return it != hull.end() && next(it) != hull.end();
}
bool bad(const line &l1, const line &l2, const line &l3){
return l1.intersect(l3) <= l1.intersect(l2);
}
bool bad(iter it){
return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}
iter update(iter it){
if(!cPrev(it)) return it;
ll x = prev(it)->intersect(*it);
line l = *it;
l.x = x;
it = hull.erase(it);
return hull.insert(it, l);
}
void addLine(ll m, ll b){
line l;
l.m = m, l.b = b, l.isq = false;
l.x = -inf;
iter it = hull.lower_bound(l);
it = hull.insert(it, l);
if(bad(it)){
hull.erase(it);
return;
}
while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
while(cNext(it) && bad(next(it))) hull.erase(next(it));
it = update(it);
if(cPrev(it)) update(prev(it));
if(cNext(it)) update(next(it));
}
ll query(ll x){
line q;
q.x = x;
q.isq = true;
iter it = --hull.lower_bound(q);
ll ret = it->eval(x);
return ret;
}
int n;
vector<pii> g[mxn];
ll ans[mxn];
ll s[mxn], v[mxn];
void dfs(int u, int p, ll dep){
if(u != p){
hull = hull2[p];
ans[u] = s[u] + v[u]*dep + query(v[u]);
addLine(-dep, ans[u]);
hull2[u] = hull;
}
for(auto e : g[u]){
if(e.st == p) continue;
dfs(e.st, u, dep + e.nd);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
fr(i, 0, n-1){
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].pb({v, w});
g[v].pb({u, w});
}
fr(i, 1, n){
cin >> s[i] >> v[i];
}
addLine(0, 0);
hull2[0] = hull;
dfs(0, 0, 0);
fr(i, 1, n) cout<<ans[i]<<' ';
cout<<endl;
return 0;
}/*
1
3
2 3 -1*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14420 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
15588 KB |
Output isn't correct |
| 3 |
Runtime error |
85 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
92 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Runtime error |
124 ms |
65536 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
128 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
143 ms |
61748 KB |
Memory limit exceeded |
| 8 |
Runtime error |
106 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
123 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
126 ms |
65536 KB |
Execution killed with signal 9 |
