#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fr first
#define sc second
#define endl '\n'
#define int long long
#define ll long long
void fopn(string name){
freopen((name+".in").c_str(),"r",stdin);
freopen((name+".out").c_str(),"w",stdout);
}
const ll INF=1e18,mod=1e9+7;
const int N=1e5+5;
struct line{
int m,b;
int operator *(int x){
return m*x+b;
}
int operator ^(line x){
return ceil((b-x.b)/(x.m-m));
}
};
int cnt=0;
line L[N];
vector<pair<int,int>> g[N];
int dp[N],v[N],s[N];
int query(int x){
int l=0,r=cnt-1;
while(l<r){
int md=(l+r)/2;
if((L[md]^L[md+1])<x) l=md+1;
else r=md;
}
return L[l]*x;
}
int remo(line ln){
if(cnt<2 || (ln^L[cnt-1])>=(L[cnt-1]^L[cnt-2])){
return cnt;
}
int l=1,r=cnt-1;
while(l<r){
int md=(l+r)/2;
if((ln^L[md])<(L[md]^L[md-1])) r=md;
else l=md+1;
}
return l;
}
void dfs(int x, int par, int d){
int mx=0,pos=0;
line ln;
if(x==1){
dp[x]=0;
L[cnt++]={0,0};
}
else{
dp[x]=query(v[x])+(d*v[x]+s[x]);
line l={-d,dp[x]};
mx=cnt;
pos=cnt=remo(l);
ln=L[cnt];
L[cnt++]=l;
}
for(auto it: g[x]){
if(it.fr!=par) dfs(it.fr,x,d+it.sc);
}
if(x!=1) cnt=mx,L[pos]=ln;
}
void solve(){
int n;cin>>n;
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
g[a].pb({b,c});
g[b].pb({a,c});
}
for(int i=2;i<=n;i++)
cin>>s[i]>>v[i];
dfs(1,0,0);
for(int i=2;i<=n;i++)
cout<<dp[i]<<' ';
//convex hull trick
}
main(){
ios;
int T=1;
//cin>>T;
while(T--){
solve();
}
}
Compilation message
harbingers.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
87 | main(){
| ^~~~
harbingers.cpp: In function 'void fopn(std::string)':
harbingers.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((name+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:14:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | freopen((name+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 2 |
Correct |
3 ms |
3156 KB |
Output is correct |
| 3 |
Correct |
48 ms |
12108 KB |
Output is correct |
| 4 |
Correct |
71 ms |
16464 KB |
Output is correct |
| 5 |
Correct |
78 ms |
20460 KB |
Output is correct |
| 6 |
Correct |
94 ms |
24508 KB |
Output is correct |
| 7 |
Correct |
62 ms |
13032 KB |
Output is correct |
| 8 |
Correct |
107 ms |
18968 KB |
Output is correct |
| 9 |
Correct |
121 ms |
21184 KB |
Output is correct |
| 10 |
Correct |
97 ms |
19268 KB |
Output is correct |
