题解：P12444 [COTS 2025] 发好奖 / Hijerarhija
Kaf_yoU
·
·
题解
清新 trick，记在小本本上了。
题意简述：
求代价不超过 $k$ 的情况下能获得的最大贡献之和。
---
考虑每个点的代价，每个点要么不选要么选，若其所有子节点内有节点选了但该点不选则设其代价为 $1$（更多显然不优）。
相当于在普通树形背包 $0$ 或 $c_i$ 的代价外额外多了一种 $1$ 的代价。发现这个东西直接从子树转移的时候需要枚举子树状态，有 $\mathcal{O}(nk^2)$ 的暴力 DP，但是显然是错误的。
正着优化十分困难！所以抛开之前所有思路，有一个妙妙 trick。
精简对于有 / 无代价的定义，如果一个点 $i$ 的代价为正整数（$1$ 或 $c_i$），则其子树内的所有点都可以花费任意代价，否则只能为 $0$。
这个表述看上去仅和子树相关，联想一个性质：子树内部的 DFS 序连续。
trick 即为在 DFS 序上 DP。具体的，设 $f_{i,j}$ 为 **DFS 序意义下**前 $i$ 个人，代价为 $j$ 的最大贡献。
对代价的三种取值分别考虑转移：
- 点 $i$ 被计算的代价为 $0$；意味着 $i$ 的子树内不能有大于 $0$ 的代价花费，只能令其去更新子树外的答案：
$$
f_{{\color{red}i}+\text{siz}_i,j}\gets\max(f_{{\color{red}i}+\text{siz}_i,j},f_{{\color{red}i},j})
$$
其中 $\text{siz}_i$ 表示 $i$ 的子树大小。
- 点 $i$ 被计算的代价为 $1$；此时可以有子树内的点被选，仅 $i$ 本身不算；直接更新下一个点：
$$
f_{{\color{red}i}+1,j+1}\gets\max(f_{{\color{red}i}+1,j+1},f_{{\color{red}i},j})
$$
- 点 $i$ 被计算的代价为 $c_i$；子树内的点依然可以选，同时 $i$ 本身也计入贡献。更新的对象与上一种相同:
$$
f_{{\color{red}i}+1,j+c_i}\gets\max(f_{{\color{red}i}+1,j+c_i},f_{{\color{red}i},j}+p_i)
$$
需要注意的是，为方便表述，上述文字中的 $i$ 和转移式中的 $i$ 意义并不完全一样，由于是按 DFS 序 DP，所以转移式中单独的 $i$ 表示的是点 $i$ 的 DFS 序（用红色标出）。
答案取 $\max f_{n+1,i\in[0,m]}$。之所以 $n+1$ 是由于该 DP 为扩散型。
---
```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int N = 5e3 + 10, kafu = -2021070767;
int n, k, dfn[N], d2i[N], siz[N], f[N][N], c[N], p[N], dcnt;
vector <int> g[N];
int cmax (int &x, int y) { return x = max (x, y); }
void DFS (int u)
{
dfn[u] = ++ dcnt, siz[u] = 1;
for (int v : g[u]) DFS (v), siz[u] += siz[v];
}
int main ()
{
cin >> n >> k;
for (int i = 2, fa; i <= n; i ++)
cin >> fa, g[fa].push_back (i);
DFS (1);
for (int i = 1; i <= n; i ++) d2i[dfn[i]] = i;
for (int i = 1; i <= n; i ++) cin >> p[i];
for (int i = 1; i <= n; i ++) cin >> c[i];
for (int i = 1; i <= n; i ++) fill (f[i], f[i] + 1 + k, kafu);
f[1][0] = 0;
for (int i = 1; i <= n; i ++)
for (int j = 0; j <= k; j ++)
{
if (f[i][j] == kafu) continue;
int ti = d2i[i];
cmax (f[i + siz[ti]][j], f[i][j]);
cmax (f[i + 1][j + 1], f[i][j]);
if (j + c[ti] <= k)
cmax (f[i + 1][j + c[ti]], f[i][j] + p[ti]);
}
// for (int i = 1; i <= n; i ++, cout << '\n')
// for (int j = 0; j <= k; j ++) cout << f[i][j] << ' ';
int ans = 0;
for (int i = 0; i <= k; i ++)
if (f[n + 1][i] != kafu) ans = max (ans, f[n + 1][i]);
cout << ans;
return 0;
}
```
---
使用 DFS 序 DP 的方便之处在于首种转移，用于方便的排除子树影响，严肃记忆.jpg。