#include "bits/stdc++.h"
using namespace std;
#define int int64_t
#define pb push_back
const int lim=3e5+100;
const int mod=1e9+7;
using pii=pair<int,int>;
int a[lim],b[lim];
vector<pii>v[lim];
int dep[lim];
int ans[lim];
deque<signed>cur;
#define calc(i) (ans[i]-a[node]*dep[i])
void dfs(int node,int par){
if(node==1){
ans[node]=0;
}else{
int l=0,r=cur.size()-1;
while(l<r){
int mid1=l+(r-l)/3,mid2=r-(r-l)/3;
int val1=calc(cur[mid1]),val2=calc(cur[mid2]);
ans[node]=LLONG_MAX;
if(val1<val2){
if(val1<ans[node])ans[node]=val1;
r=mid2-1;
}else{
if(val2<ans[node])ans[node]=val2;
l=mid1+1;
}
}
ans[node]+=b[node]+a[node]*dep[node];
}
vector<int>popped;
int sz;
while(sz=cur.size()){
if(
(ans[node]-ans[cur[0]])*(dep[cur[1]]-dep[cur[0]])>
(ans[cur[0]]-ans[cur[1]])*(dep[cur[0]]-dep[node])
){
popped.pb(cur[0]);
cur.pop_front();
}else{
break;
}
}
cur.push_front(node);
for(auto[j,c]:v[node]){
if(j^par){
dep[j]=dep[node]+c;
dfs(j,node);
}
}
cur.pop_front();
for(int i:popped){
cur.push_front(i);
}
}
void solve(){
int n;
cin>>n;
for(int i=0;i<n-1;i++){
int x,y,z;
cin>>x>>y>>z;
v[x].pb({y,z});
v[y].pb({x,z});
}
for(int i=2;i<=n;i++){
cin>>b[i]>>a[i];
}
dfs(1,0);
for(int i=2;i<=n;i++){
cout<<ans[i]<<" ";
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
Compilation message
harbingers.cpp: In function 'void dfs(int64_t, int64_t)':
harbingers.cpp:43:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
43 | while(sz=cur.size()){
| ~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
10588 KB |
Output isn't correct |
2 |
Correct |
3 ms |
11100 KB |
Output is correct |
3 |
Correct |
34 ms |
22168 KB |
Output is correct |
4 |
Correct |
49 ms |
26452 KB |
Output is correct |
5 |
Correct |
69 ms |
31240 KB |
Output is correct |
6 |
Runtime error |
80 ms |
35752 KB |
Memory limit exceeded |
7 |
Incorrect |
43 ms |
21892 KB |
Output isn't correct |
8 |
Incorrect |
79 ms |
26476 KB |
Output isn't correct |
9 |
Incorrect |
83 ms |
29344 KB |
Output isn't correct |
10 |
Incorrect |
74 ms |
27612 KB |
Output isn't correct |