Tree_Divide_conquer(fa[x]).//先求出祖先链的Dp值

Get_all_son();//将除了x父亲那一端，该重心层的点都放A中

sort(A+,A++now);//按dis_i-L_i递减排序

for(int i=,t=fa[x];i<=now;i++)

{

    for(;t!=fa[up]&&dis[t]>=dis[A[i]]-l[A[i]];t=fa[t])//up记录该重心层深度最浅的点的父亲

        ADD(t);

    UPD(A[i]);//在凸包上二分

}

Tree_Divide_conquer(....)//分治其他子树

#include<cstdio>

#include<algorithm>

typedef long long ll;

template<class T>

inline void read(T&x)

{

    x=;bool f=;char c=getchar();

    while((c<''||c>'')&&c!='-')c=getchar(); if(c=='-')f=,c=getchar();

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    x=f?-x:x;

}

const int MAXN();

const ll INF(0x7fffffffffffffff);

struct Node{int nd,nx;}bot[MAXN<<];int tot,first[MAXN];

void add(int a,int b){bot[++tot]=(Node){b,first[a]},first[a]=tot;}

int n,t,fa[MAXN],p[MAXN];ll f[MAXN],l[MAXN],dis[MAXN],s[MAXN],q[MAXN],last[MAXN];

//===================================var

int st[MAXN],tp;

ll sum(int x,int y)

{

    return f[y]+(dis[x]-dis[y])*(ll)p[x]+q[x];

}

double slope(int u,int v)

{

    return 1.0*(f[u]-f[v])/(dis[u]-dis[v]);

}

void UPD(int x)

{

int li=,ri=tp-,mid,Ans=tp;

    for(;li<=ri;)

    {

        mid=(li+ri)>>;

        if(slope(st[mid+],st[mid])<=p[x])ri=mid-,Ans=mid;else li=mid+;

    }

    if(Ans<=tp&&tp)

    {

        ll tmp=sum(x,st[Ans]);

        if(f[x]>=tmp)f[x]=tmp,last[x]=st[Ans];

    }

}

void ADD(int x)

{

    while(tp>&&slope(st[tp-],st[tp])<slope(st[tp],x))

        tp--;

    st[++tp]=x;

}

//===================================斜率优化/凸包

int size[MAXN],big[MAXN],col[MAXN],root[MAXN],flag[MAXN],all;

void Get_size(int x,int f)

{

    size[x]=;big[x]=;

    for(int v=first[x];v;v=bot[v].nx)

    if(bot[v].nd!=f&&flag[bot[v].nd]==)

    {

        Get_size(bot[v].nd,x);

        size[x]+=size[bot[v].nd];

        big[x]=std::max(big[x],size[bot[v].nd]);

    }

}

void Get_root(int x,int f)

{

    col[x]=col[f];

    for(int v=first[x];v;v=bot[v].nx)

    if(bot[v].nd!=f&&flag[bot[v].nd]==)

        Get_root(bot[v].nd,x);

    big[x]=std::max(big[x],all-size[x]);

    if(big[x]*<=all)root[col[x]]=x;

}

int A[MAXN],now;

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

void Get_ans(int x,int f)

{

    for(int v=first[x];v;v=bot[v].nx)

    if(bot[v].nd!=f&&flag[bot[v].nd]==)

        Get_ans(bot[v].nd,x);

    A[++now]=x;

}

void Tree_Dive_And_Conquer(int x)

{

int up=x;while(!flag[up])up=fa[up];

    flag[x]=;

    for(int v=first[x];v;v=bot[v].nx)

    if(!flag[bot[v].nd])

    {

        col[x]=bot[v].nd;

        Get_size(bot[v].nd,x);all=size[bot[v].nd];

        Get_root(bot[v].nd,x);

    }

    if(!flag[fa[x]])Tree_Dive_And_Conquer(root[fa[x]]);

    A[now=]=x;

    for(int v=first[x];v;v=bot[v].nx)

    if(!flag[bot[v].nd])Get_ans(bot[v].nd,x);

    std::sort(A+,A++now,cmp);

    tp=;

    for(int i=,t=fa[x];i<=now;i++)

    {

        for(;t!=fa[up]&&dis[t]>=dis[A[i]]-l[A[i]];t=fa[t])

            ADD(t);

        UPD(A[i]);

    }

    for(int v=first[x];v;v=bot[v].nx)

    if(!flag[bot[v].nd])Tree_Dive_And_Conquer(root[bot[v].nd]);

}//O(nlog^2n)

void run()

{

    Get_size(,);

    for(int i=;i<=n;i++)

    {

        big[i]=std::max(big[i],n-size[i]);

        if(big[i]*<=n)root[]=i;

    }

    flag[]=;Tree_Dive_And_Conquer(root[]);

}

//===================================点分治

int main()

{

    freopen("C.in","r",stdin);

    freopen("C.out","w",stdout);

    read(n);read(t);

    for(int i=;i<=n;i++)

    {

        read(fa[i]);read(s[i]);read(p[i]);read(q[i]);read(l[i]);

        add(i,fa[i]);add(fa[i],i);dis[i]=dis[fa[i]]+s[i];f[i]=INF;

    }

    run();

    for(int i=;i<=n;i++)printf("%lld\n",f[i]);

    return ;

}