// // Created by liasa on 13/12/2025. // #include <bits/stdc++.h> using namespace std; #define ll long long #define v vector #define lp(i, s, e) for (int i = s; i < e; ++i) #define pll pair<ll, ll> struct Line { int m; ll b; ll f(ll x) { return 1LL * m * x + b; } }; vector<int> values; const ll inf = 4e18; struct LiChao { v<Line> seg; struct Hist { int idx; int m; ll b; }; stack<Hist> st; ll sz = 1; LiChao(ll n1) { for (; sz < n1; sz *= 2) ; seg.resize(2 * sz, {0, inf}); } void update(ll i, ll l, ll r, Line &add) { ll mid = (l + r) / 2; ll x_val = values[mid]; if (add.f(x_val) < seg[i].f(x_val)) { st.push({(int)i, seg[i].m, seg[i].b}); swap(add, seg[i]); } if (l == r) return; ll x_l = values[l], x_r = values[r]; if (add.f(x_l) < seg[i].f(x_l)) { update(i * 2, l, mid, add); } else if (add.f(x_r) < seg[i].f(x_r)) update(i * 2 + 1, mid + 1, r, add); else return; } ll query(ll i, ll l, ll r, ll x) { ll res = seg[i].f(x); if (l == r) return res; ll mid = (l + r) / 2; ll mid_val = values[mid]; if (x <= mid_val) { return min(res, query(i * 2, l, mid, x)); } else return min(res, query(i * 2 + 1, mid + 1, r, x)); } }; v<ll> dp; int n; v<pll> kn; v<v<pll>> g; v<int> dpt; int values_n; void rollback(LiChao &lc, ll pic) { while (lc.st.size() > pic) { auto h = lc.st.top(); lc.seg[h.idx] = {h.m, h.b}; lc.st.pop(); } } // dp[v] = st[v] + sp[v]*dpt[v] + min(dp[u] - sp[v]*dpt[u] void dfs(int node, int par, LiChao &lc) { ll pic = lc.st.size(); int d = dpt[node]; if (node == 0) { dp[node] = 0; } else { auto [st, sp] = kn[node]; ll qu = lc.query(1, 0, values_n - 1, sp); ll my_dp = st + sp * d + qu; dp[node] = my_dp; } Line addi = {-d, dp[node]}; lc.update(1, 0, values_n - 1, addi); for (auto [it, d_add] : g[node]) { if (it != par) { dfs(it, node, lc); } } rollback(lc, pic); } void dfs1(ll node, ll par, ll dpa) { // values.push_back(dpa); dpt[node] = dpa; for (auto [it, d_add] : g[node]) { if (it != par) dfs1(it, node, dpa + d_add); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; g.resize(n); dp.resize(n); kn.resize(n); dpt.resize(n, 0); lp(i, 0, n - 1) { ll a, b, c; cin >> a >> b >> c; a--; b--; g[a].push_back({b, c}); g[b].push_back({a, c}); } dp[0] = 0; dfs1(0, -1, 0); lp(i, 1, n) { ll st, speed; cin >> st >> speed; values.push_back(speed); kn[i] = {st, speed}; } sort(values.begin(), values.end()); values.erase(unique(values.begin(), values.end()), values.end()); values_n = values.size(); LiChao lc(values_n); Line bb = {0, 0}; lc.update(1, 0, values_n - 1, bb); dfs(0, -1, lc); lp(i, 1, n) { cout << dp[i] << " "; } return 0; }