#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
vector<array<ll, 2>> g[100000];
array<ll, 2> ps[100000], all[100000];
ll oo = 1e14, re[100000];
ld xinter(array<ll, 2> a, array<ll, 2> b){
return ((ld) b[1] - a[1]) / ((ld) a[0] - b[0]);
}
ll vl(ll id, ll x){
ll l = 1, r = id;
while(l <= r){
ll m = (l + r) / 2;
if(m >= id - 1 || x <= xinter(ps[m], ps[m + 1])) r = m - 1;
else l = m + 1;
}
return ps[l][0] * x + ps[l][1];
}
void dfs(ll p, ll at, ll del, ll id){
ll res = vl(id, all[at][1]), c = all[at][0] + all[at][1] * del;
re[at] = res + c;
while(id > 2 && xinter(ps[id - 2], {-del, res + c}) <= xinter(ps[id - 2], ps[id - 1]))
--id;
array<ll, 2> aux = ps[id];
ps[id] = {-del, res + c};
for(auto [i, j] : g[at]) if(i != p)
dfs(at, i, del + j, id + 1);
ps[id] = aux;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n; cin >> n;
for(int i = 1, a, b, c; i < n; i++){
cin >> a >> b >> c; a--, b--;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
for(ll i = 1; i < n; i++)
cin >> all[i][0] >> all[i][1];
ps[0] = {1, 0};
dfs(-1, 0, 0, 1);
for(ll i = 1; i < n; i++)
cout << to_string((ll) re[i]) << " ";
cout << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |