「Luogu P2014」选课

Description

现在有 $n\ (1\leq n \leq 300)$ 个点，其中节点 $i\ (1 \leq i \leq n)$ 的父节点为 $k_i\ (0\leq k_i \leq n)$，权值为 $s_i\ (1 \leq s_i \leq 20)$，$k_i = 0$ 表示这个点没有父节点。现在需要从中选择 $m\ (1 \leq m \leq 300)$ 个点，你能选择一个点当且仅当 这个点的所有祖先节点已选 或 这个点没有父节点，求这些点的最大点权和。

Source

[Luogu]P2014

Solution

不止一个点没有父节点，说明这道题的图是一个 森林（由很多树组成）。一种经典的解决方法是，我们把每棵树的根连向一个虚拟节点—— $0$ 号节点（即 $k_i = 0$ 时依然连边）。我们把 $0$ 号节点看作必选的点，也就是说，一共要选 $m + 1$ 个点。这样就把一个森林转化成了一棵树。

这是一个有树形依赖的背包问题，所以考虑在转化后的树上做 树形DP（树形背包）。

状态：

用 $f_{u,j,k}$ 表示从 $u$ 的前 $j$ 个子节点的子树中选出 $k$ 个点的最大点权和。

初始：

$$\large { f_{u, 0, 1} = s_u }$$

从节点 $u$ 的前 $0$ 个子节点中选出 $1$ 个点的答案为 $s_u$（根据题目中的条件：只有选了节点 $u$ 才能继续选其子树中的点）。

转移：

$$\large { f_{u,j,k} = \max \begin{Bmatrix} f_{u, j - 1, k - l} + f_{v, sum_v, l} \end{Bmatrix}\\[2ex] \left( 0 \leq l \leq \min\left(k - 1,size_v \right), v \in son_u \right) }$$

其中 $v$ 是 $u$ 的第 $j$ 个子节点，$sum_v$ 表示 $v$ 的子节点个数，$size_v$ 表示 $v$ 的子树大小。在 $u$ 的子树中，从 $u$ 的前 $j$ 个子节点的子树中选出 $k$ 个点时，可以先从前 $j - 1$ 个子节点的子树中选择 $k - l$ 个点，然后在第 $j$ 个子节点 $v$ 的子树中选择 $l$ 个点，枚举 $l$，取最大值即是该状态的答案。

答案：

$$\large{\begin{aligned} &f_{root,sum_{root},m + 1} && (root\ 表示根节点) \end{aligned}}$$

答案为在根节点的子树中，从根节点的所有儿子（$sum_{root}$，即根节点的儿子个数）中选出 $m + 1$ 个点的最大点权和。此题中根节点为 $0$ 号节点（虚点）。

然而 $3$ 维的空间可能会开不下，考虑如何优化空间复杂度。

很容易发现，$u$ 是从子节点 $v$ 的状态合并而来的，所以在处理 $u$ 之前 $v$ 的状态都是已知的（即 $f_{v,sum_v,l}$ 已知）。同时状态转移与 $k$ 枚举的顺序无关，因为枚举 $k$ 时 $j - 1$ 的所有状态都已经求出来了。除此之外，状态 $k - l$ 一直在 $l$ 的前面，因此我们考虑压掉 $j$ 这一维。

状态：

用 $f_{u,j}$ 表示在 $u$ 的子树中，选出 $j$ 个点的最大点权和。

初始：

$$\large { f_{u,1} = s_u }$$

转移：

$$\large { f_{u,j} = \max \begin{Bmatrix} f_{u, j - k} + f_{v, k} \end{Bmatrix}\\[2ex] \left( 0 \leq k \leq \min\left(j - 1,size_v \right), v \in son_u \right) }$$

$size_v$ 表示 $v$ 的子树大小。注意 $j$ 应该倒序枚举，这样做的实质是：$f_{u,j-k}$ 仍然是上一次转移的状态（还没被更新），即 $f_{u-1,j-k}$ 。

答案：

$$\large{\begin{aligned} &f_{root,m + 1} && (root\ 表示根节点) \end{aligned}}$$

时间复杂度不是很好证明，应该为 $O(nm)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 300, MAXM = 300;
int n, m, tot, k, s[MAXN + 5], head[MAXN + 5], size[MAXN + 5], f[MAXN + 5][MAXN + 5];
struct Edge {
    int next, to;
} e[(MAXM << 1) + 5];

inline void addEdge(int u, int v) {
    e[++tot] = (Edge) { head[u], v };
    head[u] = tot;
}

void dfs(int u, int depth) {
    if (depth > m) return;//小优化：所选的点一定在前 m 层（节点 0 算第 0 层） 
    size[u] = 1;
    f[u][1] = s[u];//初始 
    for (int v, i = head[u]; v = e[i].to, i; i = e[i].next) {
        dfs(v, depth + 1);
        size[u] += size[v];//节点 u 的子树大小 
        for (int j = min(m + 1, size[u]); j; --j)//注意压维后要倒序枚举 
            for (int k = 0; k <= min(j - 1, size[v]); ++k)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);//转移 
    }
}

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(k), read(s[i]);
        addEdge(k, i);//k 是 i 的父节点，连一条有向边 k -> i
    }
    dfs(0, 0);//根节点是 0
    write(f[0][m + 1]);//答案
    putchar('\n');
    return 0;
}