【树套树，LCT，出栈序】P4027 [NOI2007] 货币兑换

其实是我 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;
}