| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1250812 | nanaseyuzuki | Harbingers (CEOI09_harbingers) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#pragma GCC optimization("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzd,popd")
#include <bits/stdc++.h>
/*
--> Author: Kazuki_Hoshino__8703 <--
I love Nanasaki Ai ☆*: .。. o(≒＿≒)o .。.:☆
*/
#define fi first
#define se second
#define pii pair<int, ll>
#define ll long long
using namespace std;
const int mn = 1e5 + 5, bm = (1 << 15) + 1, mod = 1532023;
const double inf = 1e18;
int n, h[mn];
ll s[mn], v[mn];
vector <pii> a[mn];
double d[mn], dp[mn];
struct line{ double a, b; };
vector <line> reina;
vector <double> pts;
double center(line x, line y){
return (double)(x.b - y.b) / (double)(y.a - x.a);
}
struct mov{
line x;
double pts;
int add;
};
vector <mov> moves;
void add(line x){
while(reina.size() && reina.back().a == x.a && reina.back().b > x.b){
moves.push_back({reina.back(), pts.back(), -1});
reina.pop_back();
pts.pop_back();
}
while(reina.size() >= 2 && center(x, reina.back()) <= pts.back()){;
moves.push_back({reina.back(), pts.back(), -1});
reina.pop_back();
pts.pop_back();
}
if(reina.size()) pts.push_back(center(x, reina.back()));
else pts.push_back(-inf);
reina.push_back(x);
moves.push_back({x, pts.back(), 1});
}
void rollback(int snap){
while((int)moves.size() > snap){
int add = moves.back().add;
line kumiko = moves.back().x;
double y = moves.back().pts;
moves.pop_back();
if(add == 1){
reina.pop_back();
pts.pop_back();
}
else{
reina.push_back(kumiko);
pts.push_back(y);
}
}
}
ll val(ll x){
int id = upper_bound(pts.begin(), pts.end(), (double)x) - pts.begin() - 1;
return reina[id].a * x + reina[id].b;
}
void dfs(int u, int p){
int snapshot = moves.size();
line kumiko = {-d[u], dp[u]};
add(kumiko);
for(auto i : a[u]){
int vv; ll c; tie(vv, c) = i;
if(vv == p) continue;
h[vv] = h[u] + 1;
d[vv] = d[u] + c;
dp[vv] = val(v[vv]) + v[vv] * d[vv] + s[vv];
dfs(vv, u);
}
rollback(snapshot);
}
void solve(){
cin >> n;
for(int i = 1; i < n; i++){
int u, vv; ll c; cin >> u >> vv >> c;
a[u].push_back({vv, c});
a[vv].push_back({u, c});
}
for(int i = 2; i <= n; i++) cin >> s[i] >> v[i];
dfs(1, 0);
for(int i = 2; i <= n; i++) cout << (long long)dp[i] << ' ';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}