Description
给定一棵 \(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;
}