#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using ll = long long;
const ll N = (ll)1e9 + 5;
const ll DEFAULT = LLONG_MAX; // for min Li Chao
struct Line {
ll m, c;
Line(ll _m = 0, ll _c = DEFAULT) : m(_m), c(_c) {}
ll eval(ll x) const {
__int128 val = (__int128)m * (__int128)x + (__int128)c;
if (val > ( (__int128)LLONG_MAX / 2 )) return LLONG_MAX;
if (val < ( (__int128)LLONG_MIN / 2 )) return LLONG_MIN;
return (ll)val;
}
ll operator()(ll x) const { return eval(x); }
};
struct Node {
Line line;
Node* left = nullptr;
Node* right = nullptr;
Node(const Line &L = Line()) : line(L) {}
};
// change record: pointer change or line change
struct Change {
bool isLineChange;
// pointer change
Node** ptrAddr = nullptr;
Node* oldPtr = nullptr;
// line change
Node* node = nullptr;
Line oldLine;
Change(Node** p, Node* old) : isLineChange(false), ptrAddr(p), oldPtr(old) {}
Change(Node* nd, const Line &oldL) : isLineChange(true), node(nd), oldLine(oldL) {}
};
vector<Change> changeLog;
vector<int> insertCheckpoints;
// recursively delete a subtree (post-order)
void deleteSubtree(Node* cur) {
if (!cur) return;
if (cur->left) { deleteSubtree(cur->left); cur->left = nullptr; }
if (cur->right) { deleteSubtree(cur->right); cur->right = nullptr; }
delete cur;
}
inline void record_ptr(Node*& p) {
changeLog.emplace_back(&p, p);
}
inline void record_line(Node* node) {
changeLog.emplace_back(node, node->line);
}
void rollbackTo(int checkpoint) {
while ((int)changeLog.size() > checkpoint) {
Change ch = changeLog.back();
changeLog.pop_back();
if (!ch.isLineChange) {
// pointer-change rollback:
Node** addr = ch.ptrAddr;
Node* cur = *addr;
// If the current pointer differs from oldPtr, delete the current subtree first
if (cur != ch.oldPtr && cur != nullptr) {
deleteSubtree(cur);
}
// restore old pointer value
*addr = ch.oldPtr;
} else {
// line-change rollback
ch.node->line = ch.oldLine;
}
}
}
void rollbackLastInsert() {
if (!insertCheckpoints.empty()) {
rollbackTo(insertCheckpoints.back());
insertCheckpoints.pop_back();
}
}
// insert impl (min Li Chao)
void insert_impl(Line newLine, Node*& root, ll l, ll r) {
if (!root) {
record_ptr(root); // record pointer before changing it
root = new Node(newLine);
return;
}
ll m = (l + r) / 2;
bool lef = newLine.eval(l) < root->line.eval(l);
bool mid = newLine.eval(m) < root->line.eval(m);
if (mid) {
record_line(root); // record the node->line before swapping
swap(root->line, newLine);
}
if (r - l == 1) return;
if (lef != mid) {
insert_impl(newLine, root->left, l, m);
} else {
insert_impl(newLine, root->right, m, r);
}
}
void insert(Line newLine, Node*& root, ll l = -N, ll r = +N) {
insertCheckpoints.push_back((int)changeLog.size());
insert_impl(newLine, root, l, r);
}
ll query(ll x, Node* root, ll l = -N, ll r = +N) {
if (!root) return DEFAULT;
ll m = (l + r) / 2;
ll res = root->line.eval(x);
if (r - l == 1) return res;
if (x < m) return min(res, query(x, root->left, l, m));
else return min(res, query(x, root->right, m, r));
}
/* ----------------- rest of your program ----------------- */
Node *root = nullptr;
int n;
vector<int> v, c;
vector<vector<pair<int,int>>> adj;
vector<ll> dp;
void dfs(int node , int p = -1 , int d = 0)
{
if(p == -1) dp[node] = 0;
else {
ll q = query(v[node], root);
dp[node] = q + (ll)v[node] * (ll)d + (ll)c[node];
}
insert(Line(-d , dp[node]) , root);
for(auto [child , len] : adj[node]) {
if(child == p) continue;
dfs(child , node , d + len);
}
rollbackLastInsert();
}
int main() {
fast;
cin >> n;
dp.assign(n, 0);
v.assign(n, 0);
c.assign(n, 0);
adj.assign(n, {});
for (int i = 0; i < n - 1; ++i) {
int u, vv, d;
cin >> u >> vv >> d;
--u; --vv;
adj[u].emplace_back(vv, d);
adj[vv].emplace_back(u, d);
}
for (int i = 1; i < n; ++i) cin >> c[i] >> v[i];
dfs(0);
for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
cout << '\n';
return 0;
}
