题解

题不怎么难，题解见下

#include <cstdio>
#include <vector>
#include <algorithm>
typedef long long LL;
const int MN = 200005;
const int MS = 2100005;
const LL Inf = 0x7fffffffffffffff;
int N, faz[MN];
std::vector<int> G[MN];
LL wgh[MN], dep[MN], dis[MN], p[MN], q[MN], b[MN], len[MN];
LL stds[MN], tds;
LL f[MN], *X = dis, *Y = f;
inline double Slope(int i, int j) {
	return X[i] == X[j] ? 1e60 : (double)(Y[j] - Y[i]) / (X[j] - X[i]);
}
int stkp[MS], valp[MS], tpp[MS];
int *istk[MN], *ival[MN], *itp[MN], it[MN];
inline void Push(int id, int u) {
	int t = it[id], tp = itp[id][t], *stk = istk[id];
	while (tp > 0 && Slope(stk[tp - 1], stk[tp]) >= Slope(stk[tp], u)) --tp;
	++t, ival[id][t] = stk[itp[id][t] = ++tp], stk[tp] = u, it[id] = t;
}
inline void Pop(int id) {
	istk[id][itp[id][it[id]]] = ival[id][it[id]];
	--it[id];
}
inline int chk(int id, LL slp) {
	int t = it[id], tp = itp[id][t], *stk = istk[id];
	if (!~tp) return -1;
	int lb = 0, rb = tp - 1, x = tp, mid;
	while (lb <= rb) {
		mid = (lb + rb) >> 1;
		if (Slope(stk[mid], stk[mid + 1]) <= slp) lb = mid + 1;
		else x = mid, rb = mid - 1;
	}
	return stk[x];
}
inline void PushAll(int i, int u) { for (; i <= N; i += i & -i) Push(i, u); }
inline void PopAll(int i) { for (; i <= N; i += i & -i) Pop(i); }
inline void GetDp(int u) {
	f[u] = Inf;
	int i = std::lower_bound(stds + 1, stds + tds + 1, dis[u] - len[u]) - stds;
	for (i = N - i + 1; i; i -= i & -i) {
		int v = chk(i, p[u]);
		if (~v) f[u] = std::min(f[u], f[v] - dis[v] * p[u] + b[u]);
	}
}
void DFS(int u) {
	dep[u] = dep[faz[u]] + 1;
	dis[u] = dis[faz[u]] + wgh[u];
	stds[++tds] = dis[u];
	b[u] = dis[u] * p[u] + q[u];
	GetDp(u);
	PushAll(N - dep[u], u);
	for (auto v : G[u]) DFS(v);
	PopAll(N - dep[u]);
	--tds;
}
int main() {
	scanf("%d%*d", &N);
	istk[1] = stkp, itp[1] = tpp, ival[1] = valp, itp[1][it[1] = 0] = -1;
	for (int i = 2; i <= N; ++i) {
		int lenl = ((i - 1) & (1 - i)) + 1;
		istk[i] = istk[i - 1] + lenl;
		itp[i] = itp[i - 1] + lenl;
		ival[i] = ival[i - 1] + lenl;
		itp[i][it[i] = 0] = -1;
	}
	for (int i = 2; i <= N; ++i) {
		scanf("%d%lld%lld%lld%lld", &faz[i], &wgh[i], &p[i], &q[i], &len[i]);
		G[faz[i]].push_back(i);
	}
	PushAll(N, 1), stds[tds = 1] = 0;
	for (auto u : G[1]) DFS(u);
	for (int i = 2; i <= N; ++i) printf("%lld\n", f[i]);
	return 0;
}