记录编号	231762	评测结果	AAAAAAAAAA
题目名称	[NOI 2014]购票	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	12.236 s
提交时间	2016-02-27 18:56:59	内存使用	18.56 MiB

#define maxn 200010ul

#define lson l,mid,t
#define rson mid+1,r,t|1

#define double_type(e) ((double)((e)))

#define ll long long

#include <vector>
#include <math.h>
#include <stdio.h>

struct pii{ll x,y;};
struct Edge{int v,nx;ll w;}edge[maxn];

typedef std::vector<pii> hull;
const double inf=1ll<<62ll,eps=1e-6;
int n,case_type,ec,dfs_clock,dfn[maxn],top[maxn],rev[maxn],fa[maxn],headlist[maxn],siz[maxn],son[maxn];
ll curp,f[maxn],dis[maxn],len[maxn],pi[maxn],qi[maxn];
hull tree[maxn*3];

//f[i]=min{f[j]-dis[j]*p[i]}+dis[i]*p[i]+q[i]

void Add_Edge(int u,int v,ll w){
	edge[++ec].v=v;
	edge[ec].w=w;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

void dfs1(int p){
	siz[p]=1;
	for(int i=headlist[p];i;i=edge[i].nx){
		dis[edge[i].v]=dis[p]+edge[i].w,dfs1(edge[i].v);
		siz[p]+=siz[edge[i].v];
		if(!son[p]||siz[edge[i].v]>siz[son[p]]) son[p]=edge[i].v;
	}
    return;
}

void dfs2(int p,int tp){
	dfn[p]=++dfs_clock,top[p]=tp,rev[dfs_clock]=p;
	if(son[p]) dfs2(son[p],tp);
	for(int i=headlist[p];i;i=edge[i].nx){
		if(edge[i].v==son[p]) continue;
		dfs2(edge[i].v,edge[i].v);
	}
	return;
}

double slope(pii a,pii b){
	if(a.y==b.y) return inf;
	return double_type(a.x-b.x)/double_type(a.y-b.y);
}

void add(hull &v,ll ins_f,ll ins_d){
	pii p=(pii){ins_f,ins_d},x,y;
	while(v.size()>1){
		x=v[v.size()-2],y=v[v.size()-1];
		if(slope(x,y)<slope(y,p)+eps) break;
		v.pop_back();
	}
	v.push_back(p);
	return;
}

void ins(int l,int r,int rt,int pos,ll ins_f,ll ins_d){
	add(tree[rt],ins_f,ins_d);
	if(l==r) return;
	int mid=(l+r)>>1,t=rt<<1;
	if(pos<=mid) ins(lson,pos,ins_f,ins_d);
	else ins(rson,pos,ins_f,ins_d);
	return;
}

ll Min(ll a,ll b){
	return a<b?a:b;
}

ll Max(ll a,ll b){
	return a>b?a:b;
}

ll get(hull &v){
	int size_=v.size(),l=0,r=size_-1,mid,fr;
	if(!size_) return inf;
	ll ans=inf;
	v.push_back((pii){inf,v[r].y});
	while(l<=r){
		mid=(l+r)>>1;
		if(slope(v[mid],v[mid+1])+eps>=curp) fr=mid,r=mid-1;
		else l=mid+1;
	}
	ans=v[fr].x-curp*v[fr].y,v.pop_back();
	return ans;
}

ll query(int l,int r,int rt,int posl,int posr,ll lim){
	if(lim<0) return inf;
	int mid=(l+r)>>1,t=rt<<1;
	ll ans1=inf,ans2=inf;
	int st=rev[l],ed=rev[r],rm=rev[mid];
	if(posl==l&&posr==r){
		if(dis[ed]-dis[st]<=lim) return get(tree[rt]);
		ans1=query(rson,mid+1,posr,lim);
		lim-=dis[ed]-dis[rm];
		ans2=query(lson,posl,mid,lim);
		return Min(ans1,ans2);
	}
	if(posr>mid) ans1=query(rson,Max(mid+1,posl),posr,lim);
	if(posl<=mid){
		if(posr>mid) lim-=dis[rev[posr]]-dis[rm];
		ans2=query(lson,posl,Min(posr,mid),lim);
	}
	return Min(ans1,ans2);
}

ll work(int x){
	curp=pi[x];
	ll ans=(ll)inf,dis_lim=len[x],ret;
	while(x&&dis_lim>=0){
		ret=query(1,n,1,dfn[top[x]],dfn[x],dis_lim);
		if(ret<ans) ans=ret;
		dis_lim-=dis[x]-dis[fa[top[x]]];
		x=fa[top[x]];
	}
	return ans;
}

ll read(){
	ll x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1ll)+(x<<3ll)+(c^48ll);
	return x;
}

int main(){
	freopen("ticket.in","r",stdin);
	freopen("ticket.out","w",stdout);
	n=read(),case_type=read();ll w;
	for(int i=2;i<=n;i++){
		fa[i]=read(),w=read(),pi[i]=read(),qi[i]=read(),len[i]=read();
		Add_Edge(fa[i],i,w);
	}
	dfs1(1),dfs2(1,1),ins(1,n,1,1,0,0);
	for(int i=2,x;i<=n;i++){
        x=rev[i],f[x]=work(x)+dis[x]*pi[x]+qi[x];
		ins(1,n,1,dfn[x],f[x],dis[x]);
	}
	for(int i=2;i<=n;i++) printf("%lld\n",f[i]);
	return 0;
}