#include<bits/stdc++.h>
typedef long long ll;using namespace std;int n;vector<pair<int,ll>>komsu[100023];ll v[100023];ll opt[100023];int par[100023][17],dep[100023];ll path[100023],ans[100023];void dfs(int pos,int root){ for(int i=1;i<17;i++){ par[pos][i]=par[par[pos][i-1]][i-1]; } int loc=pos; for(int i=17-1;i>=0;i--){ if(dep[loc]-1<(1<<i))continue; if(opt[par[loc][i]]>v[pos]){ loc=par[loc][i]; } } loc=par[loc][0]; ans[pos]+=ans[loc]+(path[pos]-path[loc])*v[pos]; loc=pos; for(int i=17-1;i>=0;i--){ if(dep[pos]-1<(1<<i))continue; int a=par[loc][i],b=par[a][0]; if(__int128_t(ans[pos]-ans[b])*__int128_t(path[a]-path[b])<=__int128_t(ans[a]-ans[b])*__int128_t(path[pos]-path[b])){ dep[pos]-=(1<<i); loc=a; } } par[pos][0]=par[loc][0]; opt[pos]=ceil(double(ans[pos]-ans[par[pos][0]])/double(path[pos]-path[par[pos][0]])); for(int i=1;i<17;i++){ par[pos][i]=par[par[pos][i-1]][i-1]; } for(auto x:komsu[pos]){ if(x.first==root)continue; path[x.first]=path[pos]+x.second; dep[x.first]=dep[pos]+1; par[x.first][0]=pos; dfs(x.first,pos); }}int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n; for(int i=1;i<n;i++){ int x,y,z;cin>>x>>y>>z; komsu[x].push_back({y,z}); komsu[y].push_back({x,z}); } for(int i=2;i<=n;i++){ cin>>ans[i]>>v[i]; } dfs(1,1); for(int i=2;i<=n;i++){ cout<<ans[i]<<" "; }}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
