思想：dfs遍历树，过程中维护根节点到当前节点的一条链，进行斜率优化dp

#include<cstdio>
#include<cstring>
#define ONLINE_JUDGE
#define int long long
#define INPUT_DATA_TYPE long long
#define OUTPUT_DATA_TYPE long long
INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){register char stack[20];register int i=0;if(x<0){x=-x;putchar('-');}if(x==0){putchar('0');return;}while(x){stack[i++]=x%10;x/=10;}while(i){putchar(stack[--i]+'0');}return;}

struct EDGE{
    int to,next;
    long long w;
    EDGE(){
        next=-1;
        return;
    }
}e[200010];

int tot,head,tail,top,path[200010],fir[200010],Q[200010],stack[200010];
long long sum[200010],p[200010],q[200010],l[200010],dp[200010];

void addEdge(int u,int v,long long w){
    e[tot].to=v;
    e[tot].w=w;
    e[tot].next=fir[u];
    fir[u]=tot;
    ++tot;
    return;
}

long long Y(int j){return dp[path[j]];}
long long X(int j){return sum[j];}
long long K(int i){return p[path[i]];}
long long B(int i){return -sum[i]*p[path[i]]-q[path[i]];}
bool checkslope(int a,int b,long long k){return Y(a)-Y(b)>=k*(X(a)-X(b));}
bool check(int a,int b,int c,int d){return (Y(a)-Y(b))*(X(c)-X(d))<=(Y(c)-Y(d))*(X(a)-X(b));}

int searchPoint(register int l,register int r,long long k){
    if(l==r) return l;
    register int mid;
    while(l<r){
        mid=(l+r)>>1;
        if(checkslope(Q[mid],Q[mid+1],k)) l=mid+1;
        else r=mid;
    }
    return l;
}

int searchHead(register int l,register int r,long long k){
    if(l==r) return l;
    register int mid;
    while(l<r){
        mid=(l+r)>>1;
        if(sum[Q[mid]]<k) l=mid+1;
        else r=mid;
    }
    return l;
}

void dfs(int u,int i){
    int ctop=0;
    register int j;
    path[i]=u;
    if(u==1){
        dp[i]=0;
        head=tail=1;
        Q[head]=1;
    }else{
        ctop=top;
        head=searchHead(1,tail+1,sum[i]-l[u]);
        int point=searchPoint(head,tail,K(i));
        dp[u]=Y(Q[point])-K(i)*X(Q[point])-B(i);
        while(head<tail&&check(Q[tail],i,Q[tail-1],Q[tail])){
            stack[top++]=Q[tail];
            --tail;
        }
        Q[++tail]=i;
    }
    for(j=fir[u];~j;j=e[j].next){
        sum[i+1]=sum[i]+e[j].w;
        dfs(e[j].to,i+1);
    }
    --tail;
    while(top>ctop){
        Q[++tail]=stack[--top];
    }
    return;
}

signed main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

    memset(fir,-1,sizeof(fir));
    register int i,t;
    register long long t2;
    int n=read();
    int T=read();
    for(i=2;i<=n;++i){
        t=read();
        t2=read();
        addEdge(t,i,t2);
        p[i]=read();
        q[i]=read();
        l[i]=read();
    }

    dfs(1,1);

    for(i=2;i<=n;++i){
        print(dp[i]);
        putchar('\n');
    }

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}