其实是我 Li-Chao-Tree 哒！！
考虑转移
\(f_x = \min f_{anc} + (d_{x} - d_{anc})p_x + q_x\) 其中 \(anc\) 为 \(x\) 的祖先，然后满足 \(d_{anc} \geq d_{x} - li_{x})\)。
考虑如果用权值线段树 + 带撤销的李超树可以维护 \(li_{x}\) 可以维护 \(li_{x} < 0\) 的情况。
但是这个题比较良心，考虑 stack 维护根到点的链。然后我们每一次在栈上二分出最早满足条件的情况。
然后建议使用 Lena and Queries 的技巧，线段树套 Li-Chao-Tree。即可。
这个题 inf 要设 \(1e18\)。
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i ++)
#define per(i, r, l) for (int i = r; i >= l; i --)
#define ls x << 1
#define rs x << 1 | 1
/*\yhx12243/ 鱼大保佑*/
/*
你说的对
但是你将在一场模拟赛中扮演“没有时间，没有实力，没有资源”的信息学竞赛选手
与没有同情心的出题人共同发掘：“60也算赢，一题夸自己”的奥赛本质。
*/
using namespace std;
typedef long long ll;
const int _ = 2e5 + 5, __ = _ * 20 + 5;
const ll inf = 1e16;
int n, t;
int rt[_ << 2], tcnt;
struct line {
ll k, b;
line (ll k = 0, ll b = inf) : k(k), b(b) {}
ll val (int x) { return 1ll * k * x + b;}
} a[_];
int tr[__];
int lc[__], rc[__];
void insert (int & x, int l, int r, int p) {
if (! x) x = ++ tcnt, tr[x] = p;
else {
int mid = (l + r) >> 1;
if (a[tr[x]].val(mid) > a[p].val(mid)) swap(tr[x], p);
if (l == r) return ;
if (a[tr[x]].val(l) > a[p].val(l)) insert(lc[x], l, mid, p);
if (a[tr[x]].val(r) > a[p].val(r)) insert(rc[x], mid + 1, r, p);
}
}
ll query (int x, int l, int r ,int v) {
if (! x) return inf;
int mid = (l + r) >> 1;
return min(a[tr[x]].val(v), v <= mid ? query(lc[x], l, mid, v) : query(rc[x], mid + 1, r, v));
}
void modify (int x, int l, int r, int v, int p) {
insert(rt[x], 0, 1e6, p);
if (l == r) return ;
int mid = (l + r) >> 1;
v <= mid ? modify(ls, l, mid, v, p) : modify(rs, mid + 1, r, v, p);
}
ll queryRange (int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) return query(rt[x], 0, 1e6, v);
int mid = (l + r) >> 1; ll ret = inf;
if (ql <= mid) ret = min(ret, queryRange(ls, l, mid, ql, qr, v));
if (qr > mid) ret = min(ret, queryRange(rs, mid + 1, r, ql, qr, v));
return ret;
}
struct EDGE {
int y;
ll z;
};
int dfc, top, dfn[_], stk[_], p[_];
ll d[_], q[_], f[_], li[__];
vector <EDGE> e[_];
void dfs1 (int x) {
for (auto & [y, z] : e[x]) dfs1(y);
dfn[x] = ++ dfc;
}
void dp (int x) {
a[x] = {-d[top], f[x]};
stk[top] = x;
modify(1, 1, n, dfn[x], x);
for (auto & [y, z] : e[x]) {
++ top, d[top] = d[top - 1] + z;
int rp = dfn[stk[lower_bound(d, d + top, d[top] - li[y]) - d]];
f[y] = queryRange(1, 1, n, dfn[y], rp, p[y]) + d[top] * p[y] + q[y];
dp(y), -- top;
}
}
int main () {
cin >> n >> t;
rep(x, 2, n) {
int fa;
ll z;
scanf("%d %lld %d %lld %lld", & fa, & z, & p[x], & q[x], & li[x]);
e[fa].push_back({x, z});
}
dfs1(1), dp(1);
rep(x, 2, n) printf("%lld\n", f[x]);
return 0;
}