#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n;
vector<pair<int,int>> adj[100001];
int aa[100001];
int bb[100001];
llo dp[100001];
vector<pair<llo,llo>> cur;
vector<pair<llo,llo>> tt;
vector<pair<int,llo>> pp[100001];
//vector<pair<llo,int>> mm[100001];
llo cc,dd,ee,ff;
llo val;
pair<llo,llo> ac;
pair<llo,llo> pc;
void dfs(int no,int par=-1,llo levv=0){
if(no==0){
dp[no]=0;
}
else{
dp[no]=levv*bb[no]+aa[no];
val=0;
if(cur.size()>1){
int low=0;
int high=cur.size()-2;
while(low<high-1){
int mid=(low+high)/2;
if(tt[mid].a<=bb[no]*tt[mid].b){
low=mid;
}
else{
high=mid;
}
}
for(int i=low;i<=high;i++){
val=min(val,cur[i+1].a*bb[no]+cur[i+1].b);
}
}
dp[no]+=val;
}
//insert {-levv,dp[no]};
ac={-levv,dp[no]};
while(cur.size()>=2){
cc=cur.back().b-ac.b;
dd=ac.a-cur.back().a;
ee=cur.back().b-cur[cur.size()-2].b;
ff=cur[cur.size()-2].a-cur.back().a;
if(ff<0){
ff=-ff;
ee=-ee;
}
if(dd<0){
dd=-dd;
cc=-cc;
}
if(cc*ff<=dd*ee){
pp[no].pb(cur.back());
// mm[no].pb(tt.back());
tt.pop_back();
cur.pop_back();
}
else{
break;
}
}
cur.pb(ac);
if(no!=0){
pc={cur.back().b-cur[cur.size()-2].b,cur[cur.size()-2].a-cur.back().a};
if(pc.b<0){
pc.a=-pc.a;
pc.b=-pc.b;
}
tt.pb(pc);
}
for(auto j:adj[no]){
if(j.a!=par){
dfs(j.a,no,levv+j.b);
}
}
if(no!=0){
cur.pop_back();
tt.pop_back();
}
while(pp[no].size()){
cur.pb(pp[no].back());
pc={cur.back().b-cur[cur.size()-2].b,cur[cur.size()-2].a-cur.back().a};
if(pc.b<0){
pc.a=-pc.a;
pc.b=-pc.b;
}
tt.pb(pc);
pp[no].pop_back();
}
/* while(mm[no].size()){
tt.pb(mm[no].back());
mm[no].pop_back();
}
*/
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i=0;i<n-1;i++){
llo aa,bb,cc;
cin>>aa>>bb>>cc;
aa--;
bb--;
adj[aa].pb({bb,cc});
adj[bb].pb({aa,cc});
}
for(int i=1;i<n;i++){
cin>>aa[i]>>bb[i];
}
dfs(0);
for(int i=1;i<n;i++){
cout<<dp[i]<<" ";
}
cout<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5612 KB |
Output is correct |
| 3 |
Correct |
60 ms |
14980 KB |
Output is correct |
| 4 |
Correct |
102 ms |
19560 KB |
Output is correct |
| 5 |
Correct |
146 ms |
24148 KB |
Output is correct |
| 6 |
Correct |
194 ms |
28152 KB |
Output is correct |
| 7 |
Correct |
118 ms |
16120 KB |
Output is correct |
| 8 |
Runtime error |
236 ms |
65536 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
188 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
178 ms |
65540 KB |
Execution killed with signal 9 |
