#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; ld xLeft; ll eval(ll x) const { return m * x + b; } }; vector<Line> hull; /* * Each addLine may remove several lines. * We record what was removed to allow undo(). */ stack<vector<Line>> history; ld intersectX(const Line &l1, const Line &l2) { return (ld)(l1.b - l2.b) / (ld)(l2.m - l1.m); } /** * Adds a new line to the convex hull. * Maintains upper/lower hull monotonicity and * records removed lines for O(1) rollback. */ void addLine(ll m, ll b) { Line newL{m, b, 0}; vector<Line> popped; // Remove all lines that are no longer needed while (!hull.empty()) { Line &l = hull.back(); if (l.m == newL.m) { if (l.b <= newL.b) { // This line is worse everywhere; no addition needed. history.push({}); return; } popped.push_back(l); hull.pop_back(); } else { ld x = intersectX(l, newL); if (x <= l.xLeft + eps) { popped.push_back(l); hull.pop_back(); } else break; } } // Compute the xLeft intersection with the previous line newL.xLeft = hull.empty() ? -1e30L : intersectX(hull.back(), newL); hull.push_back(newL); // Record what lines were popped for rollback history.push(popped); } /** * Undo the last line addition. * Restores the hull exactly to its previous state. */ void undo() { if (history.empty()) return; vector<Line> &popped = history.top(); // Remove the line we added if (!hull.empty()) hull.pop_back(); // Restore any previously popped lines for (int i = (int)popped.size() - 1; i >= 0; --i) hull.push_back(popped[i]); history.pop(); } /** * Query the minimum y value at x. * Hull must be sorted by xLeft. */ ll query(ll x) { if (hull.empty()) return INF; int low = 0, high = (int)hull.size() - 1; while (low < high) { int mid = (low + high + 1) / 2; if (hull[mid].xLeft - eps <= (ld)x) low = mid; else high = mid - 1; } return hull[low].eval(x); } vvpll adj; vll ans; vpll har; /** * Tree DP with rollback convex hull trick. */ void dfs(int u, int p = -1, ll d = 0) { if (u == 0) { // Root: initialize hull with y = 0 addLine(0, 0); } else { auto [s, t] = har[u]; ans[u] = query(t) + s + t * d; addLine(-d, ans[u]); } for (auto [v, w] : adj[u]) { if (v == p) continue; dfs(v, u, d + w); } // Roll back to previous hull state undo(); } 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'; }