这题可以点分治，但是这里写一个线段树维护凸包的做法。

首先朴素 $dp$ 的式子：

$$dp[u] = \min \{dp[v] - d_vp_u\} + q_u + d_up_u$$

其中 $d_i$ 表示 $i$ 的深度（带权值的），$v$ 是 $u$ 的一个祖先。

考虑由于 $s_i > 0$ ，所以 $-d_v$ 会随着深度变深单调递减，但是 $p_u$ 的变化没有规律。

这种情况往往只需要把最简单的斜率优化的凸包从直接 ++top 变成二分即可。可是这题还有着 $l_u$ 的限制，也就是我们能用的是一段根到这个点的后缀所建出来的凸包。

我们考虑使用线段树套单调栈。线段树的 $i$ 位置表示当前链深度 $i$ 的位置的点，然后线段树节点就是区间内建出的凸包（单调栈）。插入、查询就是普通的线段树修改。

由于出题人把问题搬到树上，我们需要撤销一次更新。在线段树节点插入时其实就是二分出应该插入的位置然后做一次修改，我们可以把修改的位置、时间拿栈存下来，就可以进行撤销了。

复杂度，每次在一个线段树节点进行修改和查询都需要二分，每次修改和查询会查 $O(\log n)$ 个点，所以复杂度是 $O(n\log^2n)$。

加上快读和快输出后在 LOJ rk8..

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
#include "assert.h"
using namespace std;
#define MAXN 400006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN];
vi G[MAXN];
int fa[MAXN] , p[MAXN];
ll s[MAXN] , q[MAXN] , l[MAXN]; // sql..

struct wkr {
	int t , idx , tp , v;
} S[MAXN << 4] ; int tp;

ll dp[MAXN] , d[MAXN]; int dep[MAXN];

double getk( int k , int j ) {
	return ( (double) dp[k] - dp[j] ) / ( d[k] - d[j] );
}

int cur;
struct stack {
	int *A , top , l , idx;
	void init( int len ) {
		A = new int[len + 3];
		memset( A , 0 , sizeof A );
		l = len , top = 0;
	}
	void ins( int x ) {
		if( !top ) {
			A[++ top] = x , S[++ tp] = (wkr){ cur , idx , 0 , 0 }; return;
		}
		int l = 1 , r = top , mid;
		while( l < r ) {
			mid = l + r >> 1;
			if( getk( A[mid] , A[mid + 1] ) > getk( A[mid] , x ) ) r = mid;
			else l = mid + 1;
		}
		int t = A[l + 1] , tt = top;
		top = l + 1 , A[top] = x;
		S[++ tp] = (wkr) { cur , idx , tt , t };
	}
	void rollback( int v , int ttp ) {
		A[top] = v , top = ttp;
	}
	ll que( ll p ) {
		if( !top ) return 1e18;
		int l = 1 , r = top , mid;
		while( l < r ) {
			mid = l + r >> 1;
			if( getk( A[mid] , A[mid + 1] ) < p ) l = mid + 1;
			else r = mid;
		}
//		cout << " >>> " << A[l] << ' ' << p << endl;
		return -d[A[l]] * p + dp[A[l]];
	}
} T[MAXN << 2] ;
void build( int rt , int l , int r ) {
	T[rt].idx = rt , T[rt].init( r - l + 1 );
	if( l == r ) return;
	int m = l + r >> 1;
	build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
}
int pu , pv;
ll que( int rt , int l , int r ) {
	if( pv <= l ) return T[rt].que( p[pu] );
	int m = l + r >> 1; ll ret = 1e18;
	if( pv <= m ) ret = que( rt << 1 , l , m );
	ret = min( ret , que( rt << 1 | 1 , m + 1 , r ) );
	return ret;
}
void upd( int rt , int l , int r ) {
	T[rt].ins( pu );
	if( l == r ) return;
	int m = l + r >> 1;
	if( dep[pu] <= m ) upd( rt << 1 , l , m );
	else upd( rt << 1 | 1 , m + 1 , r );
}

int g[MAXN][19];
void afs( int u , int fa ) {
	for( int v : G[u] ) if( v != fa ) {
		d[v] = d[u] + s[v] , dep[v] = dep[u] + 1;
		g[v][0] = u;
		rep( k , 1 , 18 ) 
			if( g[g[v][k - 1]][k - 1] ) 
				g[v][k] = g[g[v][k - 1]][k - 1];
			else break;
		afs( v , u );
	}
}

int lsj( int u , ll l ) { // last dep that d >= l
	per( k , 18 , 0 ) if( g[u][k] && d[g[u][k]] >= l ) u = g[u][k];
	return dep[u];
}

void dfs( int u , int fa ) {
	pu = u;
	if( u != 1 ) {
		pv = lsj( u , d[u] - l[u] );
		dp[u] = que( 1 , 1 , n ) + q[u] + d[u] * p[u];
	}
	cur = dep[u];
	upd( 1 , 1 , n );
	for( int v : G[u] ) if( v != fa ) 
		dfs( v , u );
	while( tp > 0 && S[tp].t >= dep[u] ) T[S[tp].idx].rollback( S[tp].v , S[tp].tp ) , -- tp;
}

void solve() {
	int t;
	cin >> n >> t;
	rep( i , 2 , n ) {
		scanf("%d%lld%d%lld%lld",fa+i,s+i,p+i,q+i,l+i);
		G[fa[i]].pb( i );
	}
	dep[1] = 1; afs( 1 , 1 );
	build( 1 , 1 , n );
	dfs( 1 , 1 );
	rep( i , 2 , n ) printf("%lld\n",dp[i]);
}

signed main() {
// 	freopen("input.in","r",stdin);
// 	freopen("ot.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}