#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;
}
}
assert(ans[node]!=LLONG_MAX);
ans[node]+=b[node]+a[node]*dep[node];
}
cur.push_front(node);
for(auto[j,c]:v[node]){
if(j^par){
dep[j]=dep[node]+c;
dfs(j,node);
}
}
cur.pop_front();
}
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();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
10588 KB |
Output isn't correct |
2 |
Incorrect |
3 ms |
11100 KB |
Output isn't correct |
3 |
Incorrect |
34 ms |
19196 KB |
Output isn't correct |
4 |
Incorrect |
50 ms |
22312 KB |
Output isn't correct |
5 |
Incorrect |
80 ms |
23892 KB |
Output isn't correct |
6 |
Incorrect |
113 ms |
28244 KB |
Output isn't correct |
7 |
Incorrect |
53 ms |
18032 KB |
Output isn't correct |
8 |
Incorrect |
79 ms |
23844 KB |
Output isn't correct |
9 |
Incorrect |
76 ms |
25156 KB |
Output isn't correct |
10 |
Incorrect |
70 ms |
22480 KB |
Output isn't correct |