题目描述
给定一颗拥有 $n$ 个节点的树,以 $1$ 号点为根节点,每个节点都有一个点权,要求找出这颗树的最小支配集上的点权和。
算法
(树形DP) $O(n)$
状态表示:
dp[v][0]
表示点 $v$ 在支配集上dp[v][1]
表示点 $v$ 不在支配集上,但被儿子节点支配dp[v][2]
表示点 $v$ 不在支配集上,但被父亲节点支配
转移方程:
$\operatorname{dp}[v][0]$ 和 $\operatorname{dp}[v][2]$ 的转移比较简单
dp[v][0] += min(dp[u][0], dp[u][1], dp[u][2]);
dp[v][2] += min(dp[u][0], dp[u][1]);
$\operatorname{dp}[v][1]$ 的转移比较特殊,因为点 $u$ 被儿子节点 $u$ 支配的同时,也可能存在点 $u$ 被它的儿子节点支配
对于存在 $\operatorname{dp}[u][0] \leqslant dp[u][1]$ 的情况,$\operatorname{dp}[v][1]$ 优先选择 $\operatorname{dp}[u][0]$
对于其他情况,可以采取反悔机制,也就是先假设点 $v$ 的所有儿子 $u$都被 它们的儿子支配,具体地,$\operatorname{dp}[v][1]$ 先把所有的 $\operatorname{dp}[u][1]$ 都选上,然后通过加上 $\min\{\{\operatorname{dp}[u][0]]\}-{\operatorname{dp}[u][1]}\}$,不妨记 $\min\{\operatorname{dp}[u][0]-\operatorname{dp}[u][1]\}$ 最大的那个儿子为点 $x$
这样我们就能把 $\operatorname{dp}[x][1]$ 从 $\operatorname{dp}[v][1]$ 中取消掉,同时选上 $\operatorname{dp}[x][0]$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
const int INF = 1001001001;
int main() {
int n;
cin >> n;
vector<vector<int>> to(n);
vector<int> w(n);
rep(i, n) {
int x, m;
cin >> x >> w[x-1] >> m;
--x;
while (m--) {
int y;
cin >> y;
--y;
to[x].push_back(y);
to[y].push_back(x);
}
}
vector dp(n, vector<int>(3));
auto dfs = [&](auto& f, int v, int p=-1) -> void {
dp[v][0] = w[v]; // v 在独立集中
dp[v][1] = 0; // v 不在支配集中,但被儿子节点支配
dp[v][2] = 0; // v 不在支配集中,但被父亲节点支配
int add = INF;
bool ok = true;
for (int u : to[v]) {
if (u == p) continue;
f(f, u, v);
dp[v][0] += min({dp[u][0], dp[u][1], dp[u][2]});
dp[v][2] += min(dp[u][0], dp[u][1]);
if (dp[u][0] <= dp[u][1]) {
ok = false;
dp[v][1] += dp[u][0];
}
else {
dp[v][1] += dp[u][1];
add = min(add, dp[u][0]-dp[u][1]);
}
}
if (ok) dp[v][1] += add;
};
dfs(dfs, 0);
int ans = min(dp[0][0], dp[0][1]);
cout << ans << '\n';
return 0;
}