제출 #266284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
266284		igm_igm	Harbingers (CEOI09_harbingers)	C++14	70 / 100	190 ms	65536 KiB

harbingers

#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;
}

• Subtask 1: 70 / 100