#include <bits/stdc++.h> using namespace std; #define MOD1 1000000007 #define MOD2 998244353 #define fir first #define sec second #define pushf push_front #define pushb push_back #define popf pop_front #define popb pop_back #define mp make_pair #define all(a) a.begin(), a.end() #define lbound(v, x) lower_bound(all(v), x) - v.begin() #define ubound(v, x) upper_bound(all(v), x) - v.begin() #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define FOR1(a) for (int _ = 0; _ < (a); ++_) #define FOR2(i, a) for (int i = 0; i < (a); ++i) #define FOR3(i, a, b) for (int i = (a); i < (b); ++i) #define RFOR1(a) for (int _ = (a)-1; _ >= 0; --_) #define RFOR2(i, a) for (int i = (a)-1; i >= 0; --i) #define RFOR3(i, a, b) for (int i = (b)-1; i >= (a); --i) #define overload3(a, b, c, d, ...) d #define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__) #define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__) typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; typedef vector<vpll> vvpll; typedef long double ld; const ll INF = 1e15; const ld eps = 1e-12; struct Line { ll m, b; ll eval(ll x) const { return m * x + b; } }; Line stk[200005]; int stk_max = 0; inline long double intersect(const Line &l1, const Line &l2) { return (long double)(l2.b - l1.b) / (long double)(l1.m - l2.m); } ll query(ll x) { int l = 0, r = stk_max - 1; while (l < r) { int m = (l + r) >> 1; if (intersect(stk[m], stk[m + 1]) < x) l = m + 1; else r = m; } return stk[l].eval(x); } int remove_pos(const Line &l) { if (stk_max < 2 || intersect(l, stk[stk_max - 1]) >= intersect(stk[stk_max - 1], stk[stk_max - 2])) return stk_max; int lpos = 1, rpos = stk_max - 1; while (lpos < rpos) { int m = (lpos + rpos) >> 1; if (intersect(l, stk[m]) < intersect(stk[m], stk[m - 1])) rpos = m; else lpos = m + 1; } return lpos; } vvpll adj; vll ans; vpll har; void dfs(int u, int p = -1, ll d = 0) { int prev_max = stk_max; Line prev_line; if (u == 0) { stk[stk_max++] = {0, 0}; } else { auto [s, t] = har[u]; ans[u] = query(t) + s + t * d; Line nl = {-d, ans[u]}; int pos = remove_pos(nl); prev_line = stk[pos]; stk_max = pos; stk[stk_max++] = nl; } for (auto [v, w] : adj[u]) { if (v == p) continue; dfs(v, u, d + w); } stk_max = prev_max; if (u != 0) stk[remove_pos({-d, ans[u]})] = prev_line; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; adj.assign(n, {}); REP(i, n - 1) { int u, v, w; cin >> u >> v >> w; u--, v--; adj[u].pushb(mp(v, w)); adj[v].pushb(mp(u, w)); } har.assign(n, {}); ans.assign(n, 0); REP(i, 1, n) cin >> har[i].fir >> har[i].sec; dfs(0); REP(i, 1, n) cout << ans[i] << ' '; cout << '\n'; }