#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1e5+10;
const int SQRT = 25;
const int MAXA = 50;
const int LOG = 27;
const int INF = 4e18+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
const vector <int> dx = {-1, 1, 0, 0};
const vector <int> dy = {0, 0, 1, -1};
int n, dp[MAXN], dep[MAXN], s[MAXN], v[MAXN];
vector <pii> adj[MAXN];
vector <int> tree[MAXN];
vector <int> vec;
struct Line {
int m, c;
int getY(int x){ return m*x+c; }
};
bool cmp(Line a, Line b, Line z){
int A = b.c-a.c, B = a.m-b.m;
int C = z.c-b.c, D = b.m-z.m;
// A/B < C/D;
if(A/B != C/D) return A/B < C/D;
return (A%B)*D < (C%D)*B;
}
vector<Line>ch[21];
void INS(Line nw, int IDX){
while(ch[IDX].size()>=2 &&
!cmp(ch[IDX][ch[IDX].size()-2], ch[IDX].back(), nw) )
ch[IDX].pop_back();
ch[IDX].pb(nw);
}
int QUE(int x, int IDX){ // cari minimum
int ret = INF;
int l=0, r=(int)ch[IDX].size()-2, mid=0;
while(r-l>=5){
mid = md;
int le = ch[IDX][mid].getY(x), ri = ch[IDX][mid+1].getY(x);
chmn(ret, min(le,ri));
if(le < ri) r = mid-1;
else l = mid+1;
}
for(int i=max(0ll, l-1); i<=min((int)ch[IDX].size(), r+1); i++)
chmn(ret, ch[IDX][i].getY(x));
return ret;
}
int idx;
int GETDP(int x){
int ret = INF;
for(int i=0; i<=idx; i++) chmn(ret, QUE(x, i));
return ret;
}
void solve(int nw, int par){
// chmn(dp[nw], dp[in] -dep[in]*v[nw] + dep[nw]*v[nw]+s[nw]);
if(nw!=1){
dp[nw] = GETDP(v[nw]) + dep[nw]*v[nw]+s[nw];
Line ins; ins.m = -dep[nw]; ins.c = dp[nw];
// cout << nw << " nw\n";
INS(ins, idx);
}
if(tree[nw].size() == 0) return;
for(int i=1; i<tree[nw].size(); i++){
int nx = tree[nw][i];
++idx; // ch baru
solve(nx,nw);
ch[idx].clear(); // ilangin
idx--;
}
solve(tree[nw][0], nw);
}
int sub[MAXN];
void dfs(int nw, int par){
sub[nw] = 1;
for(auto [nx, wei] : adj[nw]){
if(nx==par) continue;
tree[nw].pb(nx);
dep[nx] = dep[nw]+wei;
dfs(nx,nw);
sub[nw] += sub[nx];
}
}
signed main(){
// ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
freopen("harbingers.in", "r", stdin);
freopen("harbingers.out", "w", stdout);
cin >> n;
for(int i=1; i<=n-1; i++){
int u,v,w; cin>>u>>v>>w;
adj[u].pb({v,w}); adj[v].pb({u,w});
}
for(int i=2; i<=n; i++){
cin>>s[i]>>v[i];
dp[i] = INF;
}
dfs(1,0);
for(int i=1; i<=n; i++){
if(tree[i].size() == 0) continue;
for(int j=1; j<tree[i].size(); j++)
if(sub[tree[i][0]] < sub[tree[i][j]])
swap(tree[i][0], tree[i][j]);
}
Line ins; ins.m = 0; ins.c = 0; // nw = 0
INS(ins, 0);
solve(1,0);
for(int i=2; i<=n; i++) cout << dp[i] << " \n"[i==n];
}
Compilation message (stderr)
harbingers.cpp: In function 'int main()':
harbingers.cpp:109:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
109 | freopen("harbingers.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:110:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
110 | freopen("harbingers.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
