// // 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 { ll m, b; ll f(ll x) { return m * x + b; } }; vector<ll> values; const ll inf = 1e9; struct LiChao { v<Line> seg; stack<pair<int, Line>> st; ll sz = 1; LiChao(ll n1) { for (; sz < n1; sz *= 2) ; seg.resize(4 * 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({i, seg[i]}); 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 update(i * 2 + 1, mid + 1, r, add); } 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; ll n; v<pll> kn; v<v<pll>> g; v<ll> dpt; ll values_n; void rollback(LiChao &lc, ll pic) { while (lc.st.size() > pic) { auto [i, segi] = lc.st.top(); lc.seg[i] = segi; 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(); ll d = dpt[node]; 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, my_dp}; 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; }