Description

P3780 [SDOI2017] 苹果树

给定一棵 \(n\) 个点的树，每个点有若干个价值相同的苹果，儿子能摘至少一个仅当父亲被摘至少一个。

给定 \(k\)，设 \(h\) 为你摘的苹果的最大深度，你做多能摘 \(k+h\) 个，求最大价值。

对于所有数据，\(1\le n\le 5\times 10^4\)，\(1\le k\le 5\times 10^5\)，\(1\le nk\le 2.5\times 10^7\)。

Solution

深度的条件可以转化为免费选一条链，得到链每个点上的一个苹果。

考虑枚举这条链，链将苹果分为三类：链上每个点的一个免费苹果，链左边的与链上剩余付费苹果，链右边的付费苹果。第一类可以简单处理出每个点到根路径上的价值和，对于第二三类考虑 DP 后对每条链合并。

设 \(f_{i,k,j}\) 为考虑根到节点 \(i\) 的链及其左边的，\(i\) 的前 \(k\) 棵子树里的，除去链上每个点免费的苹果，摘了 \(j\) 个最大的价值。转移分两种：

• 父亲将链及左边转移给儿子：枚举 \(u\) 的每个儿子 \(v\)，设 \(v\) 为 \(u\) 从左到右的第 \(t\) 个儿子。先将 \(f_{u,t-1}\) 的值拷贝给 \(f_{v,0}\)，然后加入 \(v\) 的苹果，对 \(f_{v,0}\) 跑多重背包（可以不选）。由于要减去一个免费的，所以只能加入 \(a_{v}-1\) 个苹果。转移后递归 \(v\) 的子树。
• 儿子将子树转移给父亲：沿用上文的 \(u,v,t\)。递归 \(v\) 的子树后，更新 \(f_{u,t}\)。由于 \(v\) 处不一定选了苹果，所以要强制加入一个 \(v\) 苹果来更新：\(\displaystyle f_{u,t,j}=\max\{f_{u,t-1,j},f_{v,\operatorname{sonsize}(v),j-1}+val_{v}\}\)。

实现的时候不用记第二维。多重背包要用单调队列优化，如果您不会可以先去学习 P1776 宝物筛选 。

同理，设 \(g_{i,k,j}\) 为考虑根到节点 \(i\) 的链右边的（不包括这条链），\(i\) 的后 \(k\) 棵子树里的的苹果，摘了 \(j\) 个最大的价值。转移类似：

• 父亲将链右边转移给儿子：枚举 \(u\) 的每个儿子 \(v\)，设 \(v\) 为 \(u\) 从右到左的第 \(t\) 个儿子。将 \(g_{u,t-1}\) 的值拷贝给 \(g_{v,0}\)，然后递归 \(v\) 的子树。
• 儿子将子树转移给父亲：沿用 \(u,v,t\)。递归 \(v\) 的子树后，复制一份 \(tmp=g_{v,\operatorname{sonsize}(v)}\)，用 \(v\) 节点上的苹果对 \(tmp\) 跑多重背包（不能不选），然后来更新 \(g_{u,t}\) 即可：\(\displaystyle g_{u,t,j}=\max\{g_{u,t-1,j},tmp_{j}\}\)。

为了方便，实现时 \(a_{v}\) 次不能不选的背包可以转化成 \(a_{v}-1\) 可以可以不选的背包与最后一次必选。

时间复杂度 \(\mathcal{O}(nk)\)。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;
namespace Milkcat {
	typedef long long LL;
	typedef pair<LL, LL> pii;
    typedef vector<LL> poly;
	const int N = 2e4 + 5;
	int n, k, u, v, ans, a[N], val[N], sum[N], siz[N];
	vector<int> G[N], f[N], g[N];
	void update(vector<int>& f, int c, int v) {
		vector<int> g(f.size()); deque<int> q;
		for (int i = 0; i <= k; i ++) {
			while (!q.empty() && i - q.front() > c) q.pop_front();
			while (!q.empty() && f[i] - v * i > f[q.back()] - v * q.back()) q.pop_back();
			q.push_back(i), g[i] = f[q.front()] + v * (i - q.front());
		}
		g.swap(f);
	}
	void dfs1(int u, int fa) {
		update(f[u], a[u] - 1, val[u]);
		sum[u] = sum[fa] + val[u], siz[u] = 1;
		for (int v : G[u]) {
			if (v == fa) continue;
			f[v] = f[u], dfs1(v, u), siz[u] += siz[v];
			for (int i = 1; i <= k; i ++)
				f[u][i] = max(f[u][i], f[v][i - 1] + val[v]);
		}
	}
	void dfs2(int u, int fa) {
		reverse(G[u].begin(), G[u].end());
		for (int v : G[u]) {
			if (v == fa) continue;
			g[v] = g[u], dfs2(v, u);
			vector<int> tmp(g[v]);
			update(tmp, a[v] - 1, val[v]);
			for (int i = 1; i <= k; i ++)
				g[u][i] = max(g[u][i], tmp[i - 1] + val[v]);
		}
	}
	int main() {
		cin >> n >> k;
		for (int i = 1; i <= n; i ++) {
			cin >> u >> a[i] >> val[i];
			if (u) G[u].pb(i), G[i].pb(u); 
		}
		f[1].resize(k + 2), g[1].resize(k + 2);
		dfs1(1, 0), dfs2(1, 0);
		for (int i = 1; i <= n; i ++) {
			if (siz[i] > 1) continue;
			for (int j = 0; j <= k; j ++)
				ans = max(ans, f[i][j] + g[i][k - j] + sum[i]);
		}
		cout << ans << '\n';
		return 0;
	}
	void clear() {
		f[1].clear(), g[1].clear(), ans = 0;
		for (int i = 1; i <= n; i ++) G[i].clear();
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
    int T = 1; cin >> T;
    while (T --) Milkcat::main(), Milkcat::clear();
    return 0;
}