\(\text{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\) 即可

\(\text{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\n", val[rt[1]]);

}

巴特西

「CEOI2019」魔法树

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章