记录编号	260611	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]购票	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	7.199 s
提交时间	2016-05-14 09:25:49	内存使用	25.49 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const long long INF=(long long)1e18;
const int maxn=200010;
int cnt,fir[maxn],to[maxn],nxt[maxn],son[maxn],sz[maxn],fa[maxn],n,t;
long long val[maxn],P[maxn],Q[maxn],S[maxn],F[maxn],L[maxn];
void addedge(int a,int b,long long c){
	nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;val[cnt]=c;
}

void DFS(int x){
	sz[x]=1;
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x]){
			fa[to[i]]=x;
			S[to[i]]=S[x]+val[i];
			DFS(to[i]);
			sz[x]+=sz[to[i]];
			if(sz[son[x]]<sz[to[i]])
				son[x]=to[i];
		}
}

int top[maxn],ID[maxn],RID[maxn],tot;
void DFS(int x,int tp){
	ID[x]=++tot;RID[tot]=x;top[x]=tp;
	if(son[x])DFS(son[x],tp);
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa[x]&&to[i]!=son[x])
			DFS(to[i],to[i]);
}

struct Slope{
	vector<int>id;
	void Insert(int x){
		int p=id.size()-1;
		id.push_back(x);
		while(true){
			if(p<=0)break;
			if(1.0*(F[id[p]]-F[id[p-1]])/(S[id[p]]-S[id[p-1]])<1.0*(F[id[p+1]]-F[id[p]])/(S[id[p+1]]-S[id[p]]))break;
			id.pop_back();id.pop_back();id.push_back(x);p--;
		}
		return; 
	}
	
	long long Query(int p){
		int p1=-1,p2;
		for(int i=20;i>=0;i--){
			p2=p1+(1<<i);
			if(p2>=id.size()-1)continue;
			if(1.0*(F[id[p2+1]]-F[id[p2]])/P[p]<=1.0*(S[id[p2+1]]-S[id[p2]]))
				p1+=1<<i;
		}
		p1+=1;
		return F[id[p1]]+(S[p]-S[id[p1]])*P[p]+Q[p];
	}
}slope[maxn<<2];

long long Query(int x,int l,int r,int a,int b,int p){
	if(l>=a&&r<=b)
		return slope[x].Query(p);
		
	int mid=(l+r)>>1;
	long long ret=INF;
	if(a<=mid)
		ret=Query(x<<1,l,mid,a,b,p);
	if(mid<b)
		ret=min(ret,Query(x<<1|1,mid+1,r,a,b,p));
	return ret;		
}

void Insert(int x,int l,int r,int p){
	slope[x].Insert(p);
	if(l==r)return;
	int mid=(l+r)>>1;
	if(mid>=ID[p])
		Insert(x<<1,l,mid,p);
	else
		Insert(x<<1|1,mid+1,r,p);	
}

long long Get_ans(int p){ 
	int pos=fa[p];
	long long ret=INF;
	while(pos){
		if(S[p]-L[p]>S[pos])break;
		int p1=ID[top[pos]]-1;
		for(int i=20;i>=0;i--)
			if(p1+(1<<i)<ID[pos]&&S[RID[p1+(1<<i)]]<S[p]-L[p])
				p1+=1<<i;		
		ret=min(ret,Query(1,1,n,p1+1,ID[pos],p));
		pos=fa[top[pos]];
	}
	return ret;
}

void Solve(int x){
	F[x]=x==1?0:Get_ans(x);
	Insert(1,1,n,x);
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=son[x])
			Solve(to[i]);
	if(son[x])
		Solve(son[x]);		
	return;
}

int main(){
#ifndef ONLINE_JUDGE 
	freopen("ticket.in","r",stdin);
	freopen("ticket.out","w",stdout);
#endif 
	scanf("%d%d",&n,&t);
	for(int i=2,a,b;i<=n;i++){
		scanf("%d%d%lld%lld%lld",&a,&b,&P[i],&Q[i],&L[i]);
		addedge(a,i,b*1ll);
	}
	
	DFS(1);
	DFS(1,1);
	
	Solve(1);
	for(int i=2;i<=n;i++)
		printf("%lld\n",F[i]);
	return 0;
}