#include <bits/stdc++.h> #define all(x) begin(x), end(x) using namespace std; using ll = long long; const char nl = '\n', sp = ' '; const int N = 1e5 + 9; struct Line { int m; ll c; ll eval(ll x) { return m * x + c; } }; struct LiChaoNode { Line line; int l, r; LiChaoNode() { line = Line({0, numeric_limits<long long>::max() / 2}); l = 0, r = 0; } LiChaoNode(Line line) : line(line), l(0), r(0) { } }; vector<LiChaoNode> t; int T; int upd(int pre, Line nw, int l, int r) { int m = (l + r) / 2; int id = ++T; t[id].line = t[pre].line; bool lef = nw.eval(l) < t[id].line.eval(l); bool mid = nw.eval(m) < t[id].line.eval(m); if (mid) swap(t[id].line, nw); if (l == r) return id; if (lef != mid) { if (!t[pre].l) t[id].l = ++T, t[T] = LiChaoNode(nw); else t[id].l = upd(t[pre].l, nw, l, m); t[id].r = t[pre].r; } else { if (!t[pre].r) t[id].r = ++T, t[T] = LiChaoNode(nw); else t[id].r = upd(t[pre].r, nw, m + 1, r); t[id].l = t[pre].l; } return id; } ll Query(int cur, int x, int l, int r) { ll val = t[cur].line.eval(x); int m = (l + r) / 2; if (l < r) { if (x <= m && t[cur].l) val = min(val, Query(t[cur].l, x, l, m)); if (x > m && t[cur].r) val = min(val, Query(t[cur].r, x, m + 1, r)); } return val; } struct PersistentLiChaoTree { int L, R; vector<int> roots; PersistentLiChaoTree() { roots = {1}; T = 1; L = -1e9; R = 1e9; } PersistentLiChaoTree(int n, int L, int R) : L(L), R(R) { T = 1; roots.push_back(1); t.resize(n * 30); } int add_line(int i, Line line) { int root = upd(roots[i], line, L, R); roots.push_back(root); return root; } ll query(int i, int x) { return Query(roots[i], x, L, R); } }; void solve() { int n; cin >> n; vector<vector<pair<int, int> > > g(n); for (int i = 0; i < n - 1; i++) { int u, v, w; cin >> u >> v >> w; --u, --v; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } vector<pair<int, int> > a(n); for (int i = 1; i < n; i++) { cin >> a[i].first >> a[i].second; } PersistentLiChaoTree lc(n, 0, 1e9 + 1); vector<int> ans(n); vector<int> versions(n); lc.add_line(0, {0, 0}); versions[0] = 1; vector<int> cost(n); int cnt = 1; auto dfs = [&](auto &&dfs, int u, int p, int d) -> void { auto &[s, v] = a[u]; if (u != 0) { cost[u] = lc.query(versions[p], v) + s + v * d; lc.add_line(versions[p], {-d, cost[u]}); versions[u] = ++cnt; } for (auto &[v, w]: g[u]) { if (v == p) continue; dfs(dfs, v, u, d + w); } }; dfs(dfs, 0, -1, 0); for (int i = 1; i < n; i++) { cout << cost[i] << sp; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); #ifdef LOCAL freopen("../in.txt", "r", stdin); freopen("../out.txt", "w", stdout); #endif int t = 1; // cin >> t; while (t--) { solve(); } }