// 01001100 01001111 01010100 01000001 \\
// \\
// ╦ ╔═╗╔╦╗╔═╗ \\
// ║ ║ ║ ║ ╠═╣ \\
// ╩═╝╚═╝ ╩ ╩ ╩ \\
// \\
// 01001100 01001111 01010100 01000001 \\
#include <bits/stdc++.h>
using namespace std;
#define N 100001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
ll V[N];
ll d[N];
int s[N];
ll dp[N];
vector<pll> ad[N];
vector<pii> a[N];
vector<pll> lines;
bool lesser(pair<__int128, __int128> p, pair<__int128, __int128> q){
return p.ff * q.ss < q.ff * p.ss;
}
bool comp(pll l1, pll l2, pll l3){
return lesser({l2.ss - l3.ss, l3.ff - l2.ff}, {l1.ss - l2.ss, l2.ff - l1.ff});
}
void insert(pll l, int v){
while(lines.size() > 1 && comp(lines[lines.size() - 2], lines.back(), l)){
ad[v].append(lines.back());
lines.pop_back();
}
lines.append(l);
}
ll get(pll l, ll x){
return l.ff * x + l.ss;
}
ll query(int x){
int ans = 0;
for(int i = 524288; i > 0; i /= 2)
if(ans + i < lines.size() && get(lines[ans + i], x) < get(lines[ans + i - 1], x))
ans += i;
return get(lines[ans], x);
}
void dfs(int v, int u){
if(v > 1)
dp[v] = query(V[v]) + V[v] * d[v] + s[v];
insert({-d[v], dp[v]}, v);
for(auto & [i, j] : a[v]){
if(i == u) continue;
d[i] = d[v] + j;
dfs(i, v);
}
lines.pop_back();
while(!ad[v].empty()){
lines.append(ad[v].back());
ad[v].pop_back();
}
}
void solve(){
int n, p, q, r;
cin >> n;
for(int i = 1; i < n; i++){
cin >> p >> q >> r;
a[p].append({q, r});
a[q].append({p, r});
}
for(int i = 2; i <= n; i++){
cin >> p >> q;
s[i] = p, V[i] = q;
}
dfs(1, 0);
for(int i = 2; i <= n; i++)
cout << dp[i] << ' ';
}
int terminator(){
L0TA;
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |