「CEOI2019」魔法树

( ext{Solution})

设 (f_{x,i}) 表示以 (x) 为根的子树 (i) 天后的最大收益
那么 (f_{x,i} = max(f_{x,i-1},w_x [d[x] ge i] + sum f_{v,i}))
这样的转移时 (O(nk)) 的，只能拿到 (34pts)
再加上其他的部分分也只有 (48pts)

正解是在这个 (dp) 上优化
我们发现很多状态都是没用的
观察到 (x) 各个状态的值由 (v) 对应的状态合并上来
那么就可以考虑线段树合并
开 (n) 棵线段树代替 (f) 的第二维，也就是时间这一维
转移就成线段树的合并操作了
但发现 (f) 的值是前缀最大值，需要我们获得前缀最大值之后再合并（相加）才对
那么线段树合并的时候维护两棵线段树前缀最大值，给对方
合并完子树后考虑加入当前节点的贡献
(x) 会对它的线段树 (d_x) 以后的值产生影响
并且此时还需取出 (d_x) 前的最大值加上 (w_x) 才是正确的贡献
对 (d_x) 以后的值取 (max) 即可

( ext{Code})

#include <cstdio>
#include <iostream>
#define re register
using namespace std;
typedef long long LL;

const int N = 1e5 + 5;
int n, m, k, fa[N], tot, h[N];
struct node{int d, w;}a[N];
struct edge{int to, nxt;}e[N];
inline void add(int x, int y){e[++tot] = edge{y, h[x]}, h[x] = tot;}

inline void read(int &x)
{
	x = 0; char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}

int size, ls[N << 5], rs[N << 5], rt[N];
LL val[N << 5], tag[N << 5];

inline void pushdown(int p)
{
	if (!tag[p]) return;
	if (ls[p]) val[ls[p]] += tag[p], tag[ls[p]] += tag[p];
	if (rs[p]) val[rs[p]] += tag[p], tag[rs[p]] += tag[p];
	tag[p] = 0;
}

void update(int &p, int l, int r, int x, LL v)
{
	if (!p) p = ++size, ls[p] = rs[p] = val[p] = tag[p] = 0;
	val[p] = max(val[p], v);
	if (l == r) return;
	pushdown(p);
	int mid = (l + r) >> 1;
	if (x <= mid) update(ls[p], l, mid, x, v);
	else update(rs[p], mid + 1, r, x, v);
}

LL query(int p, int l, int r, int x)
{
	if (!p || r <= x) return val[p];
	pushdown(p);
	int mid = (l + r) >> 1; LL res = query(ls[p], l, mid, x);
	if (x > mid) res = max(res, query(rs[p], mid + 1, r, x));
	return res;
}

int merge(int x, int y, LL tagx, LL tagy, int l, int r)
{
	if (!x && !y) return 0;
	if (!y){val[x] += tagx, tag[x] += tagx; return x;}
	if (!x){val[y] += tagy, tag[y] += tagy; return y;}
	if (l == r)
	{
		tagx = max(tagx, val[y]), tagy = max(tagy, val[x]);
		val[x] = max(val[x] + tagx, val[y] + tagy);
		return x;
	}
	pushdown(x), pushdown(y);
	int mid = (l + r) >> 1;
	LL valx = val[ls[x]], valy = val[ls[y]];
	ls[x] = merge(ls[x], ls[y], tagx, tagy, l, mid);
	rs[x] = merge(rs[x], rs[y], max(tagx, valy), max(tagy, valx), mid + 1, r);
	val[x] = max(val[ls[x]], val[rs[x]]);
	return x;
}

void dfs(int x)
{
	for(re int i = h[x]; i; i = e[i].nxt) 
		dfs(e[i].to), rt[x] = merge(rt[x], rt[e[i].to], 0, 0, 1, k);
	if (a[x].d) update(rt[x], 1, k, a[x].d, query(rt[x], 1, k, a[x].d) + a[x].w);
}

int main()
{
	read(n), read(m), read(k);
	for(re int i = 2; i <= n; i++) read(fa[i]), add(fa[i], i);
	for(re int i = 1, v; i <= m; i++) read(v), read(a[v].d), read(a[v].w);
	dfs(1), printf("%lld
", val[rt[1]]);
}