#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e9, inf = 2e9,MAXN = 1e7+1;
const int N = 1e5+1;
vector<signed> s(N),v(N),d(N);
vi dp(N);
vector<pair<signed,signed>> edges[N];
struct Line {
signed m;
int b;
int eval(int x) {
return 1LL*m*x+b;
}
};
Line lines[MAXN];
stack<pair<signed,Line>> upds;
int lft[MAXN],rgt[MAXN];
int ids = 0;
struct LiChao {
int crenode() {
lines[ids] = {inf,inf};
lft[ids] = -1;
rgt[ids] = -1;
ids++;
return ids-1;
}
int leftchild(int node) {
if (lft[node] == -1) lft[node] = crenode();
return lft[node];
}
int rightchild(int node) {
if (rgt[node] == -1) rgt[node] = crenode();
return rgt[node];
}
void update(int node, int l,int r,Line line) {
if (line.m == inf && line.b == inf) return;
int m = (l+r) >> 1;
bool good = lines[node].eval(l) > line.eval(l);
bool goodmid = lines[node].eval(m) > line.eval(m);
if (goodmid) {
upds.push({node,lines[node]});
swap(lines[node].m,line.m),swap(lines[node].b,line.b);
}
if (l == r) return;
if (goodmid != good) update(leftchild(node),l,m,line);
else update(rightchild(node),m+1,r,line);
};
int query(int node,int l,int r,int x) {
if (l == r) return lines[node].eval(x);
int m = (l+r) >> 1;
if (x <= m) {
if (lft[node] == -1) return lines[node].eval(x);
return min(lines[node].eval(x),query(leftchild(node),l,m,x));
}
if (rgt[node] == -1) return lines[node].eval(x);
return min(lines[node].eval(x),query(rightchild(node),m+1,r,x));
}
void rollback(int k) {
while (k--) {
lines[upds.top().ff] = upds.top().ss;
upds.pop();
}
}
}LC;
void dfs(int node,int p,int der = 0) {
d[node] = der;
if (node > 1) {
dp[node] = 1LL*s[node]+1LL*v[node]*d[node]+LC.query(0,0,LIM,v[node]);
}
else dp[node] = 0;
int crea = upds.size();
LC.update(0,0,LIM,{-d[node],dp[node]});
int crea2 = upds.size();
for (auto it : edges[node]) {
if (it.ff == p) continue;
dfs(it.ff,node,der+it.ss);
}
LC.rollback(crea2-crea);
}
void solve() {
int n;
cin >> n;
for (int i=1;i<n;i++) {
int a,b,c;
cin >> a >> b >> c;
edges[a].push_back({b,c});
edges[b].push_back({a,c});
}
for (int i=2;i<=n;i++) cin >> s[i] >> v[i];
int root = LC.crenode();
dfs(1,1);
for (int i=2;i<=n;i++) cout << dp[i] << ' ';
cout << '\n';
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Dodi
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |