记录编号	164220	评测结果	AAAEEAAAAA
题目名称	[NOI 2014]购票	最终得分	80
用户昵称	Chenyao2333	是否通过	未通过
代码语言	C++	运行时间	4.462 s
提交时间	2015-05-29 14:42:46	内存使用	17.28 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e17;
const int L_N=2e5+10;

int N;
int fa[L_N];
LL to_fa_len[L_N],P[L_N],Q[L_N],len_limit[L_N];
LL dis[L_N];
LL F[L_N];
bool be_sol[L_N];

vector<int> G[L_N];

int links[L_N],ln;

int sz[L_N];

int MI,RT,SZ;
void dfs_size(int u){
	sz[u]=1;
	int mx=0;
	
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(be_sol[v]) continue;
		dfs_size(v);
		sz[u]+=sz[v];
		mx=max(mx,sz[v]);
	}
	
	mx=max(mx,SZ-sz[u]);
	//printf("u=%d mx=%d\n",u,mx);
	
	if(mx<MI){
		MI=mx;
		RT=u;
	}
}
int find_wei_center(int u,int size){
	MI=size+1,RT=u,SZ=size;
	dfs_size(u);
	return RT;
}

int stack[L_N],s_st,s_ed;
double slope[L_N];

double calc_slope(int i,int j){
	return double(F[j]-F[i]) / double (dis[j]-dis[i]);
}

void insert(int i){
	while((s_ed-s_st+1)>=2 && calc_slope(i,stack[s_st]) > calc_slope(stack[s_st+1],stack[s_st])){
		s_st++;
	}
	s_st--;
	stack[s_st]=i;
}

void upd(int i,int j){
	LL d=dis[i]-dis[j];
	if(d<=len_limit[i]){
		F[i]=min(F[i],F[j]+d*P[i]+Q[i]);
	}
}

void calc(int i){
	if(s_st>s_ed) return;
	
	int l=s_st, r=s_ed;
	while(l<r){
		int mid=(l+r)/2;
		
		double k=calc_slope(stack[mid],stack[mid+1]);
		if(k>P[i]) r=mid;
		else l=mid+1;
	}
	
	int j=stack[l];
	F[i]=min(F[i],F[j]+(dis[i]-dis[j])*P[i]+Q[i]);
}

int rights[L_N],rn;

void dfs_rights(int u){
	//printf("dfs_calc=%d\n",u);
	rights[++rn]=u;
	for(int i=0;i<G[u].size();i++){
		int v=G[u][i];
		if(be_sol[v]) continue;
		dfs_rights(v);
	}
}

bool cmp_right(int a,int b){
	return dis[a]-len_limit[a]>dis[b]-len_limit[b];
}

void solve(int u,int size){
	//printf("solve(%d,%d):\n",u,size);
	if(size<=1) return;
	
	int cen=find_wei_center(u,size);
	//printf("cen=%d\n",cen);
	be_sol[cen]=true;
	solve(u,size-sz[cen]);
	

	ln=0;
	int tmp_x=cen;
	while(true){
		links[++ln]=tmp_x;
		if(tmp_x==u) break;
		tmp_x=fa[tmp_x];
		upd(cen,tmp_x);	
	}
	rn=0;
	for(int i=0;i<G[cen].size();i++){
		int v=G[cen][i];
		if(be_sol[v]) continue;
		dfs_rights(v);
	}
	
	sort(rights+1,rights+1+rn,cmp_right);
	
	
	s_ed=N,s_st=N+1;
	int ln_p=1;
	for(int i=1;i<=rn;i++){
		LL min_d=dis[rights[i]]-len_limit[rights[i]];
		while(ln_p<=ln && dis[links[ln_p]]>=min_d){
			insert(links[ln_p]);
			ln_p++;
		}
		
		calc(rights[i]);
	}
	
	for(int i=0;i<G[cen].size();i++){
		int v=G[cen][i];
		if(be_sol[v]) continue;
		solve(v,sz[v]);
	}
	
}

int main(){
	freopen("ticket.in","r",stdin);
	freopen("ticket.out","w",stdout);

	int T; scanf("%d %d",&N,&T);
	for(int i=2;i<=N;i++){
		scanf("%d %lld %lld %lld %lld",fa+i,to_fa_len+i,P+i,Q+i,len_limit+i);
		G[fa[i]].push_back(i);
	}

	for(int i=2;i<=N;i++){
		F[i]=INF;
		dis[i]=dis[fa[i]]+to_fa_len[i];
	}
	
	solve(1,N);
	
	for(int i=2;i<=N;i++) printf("%lld\n",F[i]);
	return 0;
}