最小支配集问题
题意
给定一棵树，选择一个点后可以覆盖该点以及所有与之相邻的点，求选择最少的点使整棵树被覆盖。
思路
定义三种状态：
- dp[u][0]:选择u节点后，使整棵子树被覆盖的最少点集
- dp[u][1]:不选u节点但被子节点覆盖，使整棵子树被覆盖的最少点集
- dp[u][2]:不选u节点但被父节点覆盖，使整棵子树被覆盖的最少点集
状态转移：
- 选择u节点，则其子节点可选可不选，取最少点集方案求和。
$$ dp[u][0] = \sum_{v \in son[u]} min(dp[v][0], dp[v][1],dp[v][2]); $$
- 不选u节点但被子节点覆盖，意味着有一个子节点一定被选择，其他的子节点可选可不选取最少点集方案求和。
$$ dp[u][1] = min(dp[u][1], dp[x][0] + \sum_{v \in son[u] \ \&\& \ v \neq x} min(dp[v][0], dp[v][1]) ); $$
变换公式：
$$ dp[u][1] = min(dp[u][1], dp[x][0] + \sum_{v \in son[u]} min(dp[v][0], dp[v][1]) - min(dp[x][0], dp[x][1])); $$
其中 $\sum_{v \in son[u]} min(dp[v][0], dp[v][1])$ 是定值，决定大小的是 $dp[x][0] - min(dp[x][0], dp[x][1])$。
- 不选u节点但被父节点覆盖，则其子节点可选可不选，但不选时无法被u节点覆盖，取最少的点集方案求和。
$$ dp[u][2] = \sum_{v \in son[u]} min(dp[v][0], dp[v][1]); $$
这里可以发现 dp[u][2] 的值就是上面说的定值，所以 dp[u][1] 在计算过程中只需计算 $dp[x][0] - min(dp[x][0], dp[x][1])$ 的最小值。
初始化DP数组
当u节点被选择时，点集数加一，同时 dp[u][1] 要计算 $dp[x][0] - min(dp[x][0], dp[x][1])$ 的最小值，需要初始化为最大值。
最后，因为根节点是不可能被父节点覆盖的，所以答案取 $min(dp[1][1], dp[1][0])$。
参考代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int N = 1e5 + 10;
int n;
vector<int> g[N];
ll dp[N][3];
void dfs(int u, int fa)
{
dp[u][0] = 1;
dp[u][1] = INF;
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += min({dp[v][0], dp[v][1], dp[v][2]});
dp[u][1] = min(dp[u][1], dp[v][0] - min(dp[v][0], dp[v][1]));
dp[u][2] += min(dp[v][0], dp[v][1]);
}
dp[u][1] = dp[u][2];
}
int main()
{
cin >> n;
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, -1);
cout << min(dp[1][0], dp[1][1]);
return 0;
}
推荐例题： P2899 [USACO08JAN] Cell Phone Network G
K度最小支配集问题
题意
给定一棵树，选择一个点后可以覆盖所有与之最短距离不超过 k 的点，求选择最少的点覆盖整棵树。
思路
定义状态
- dp[u][0]：记录以节点u为根的子树中，未被覆盖的最远距离（即需要被覆盖的需求）
- dp[u][1]：记录以节点u为根的子树中，最近的覆盖点到u的距离（即提供的覆盖能力）
状态转移
如果最近的覆盖点到u的距离超过k，则可能需要将其未被覆盖距离设为0。
如果未被覆盖的最远距离加上最近的覆盖距离不超过k，说明该节点已被覆盖，重置状态。
若未被覆盖的最远距离等于k，则必须在此节点放置覆盖点，并更新状态。
最后，若根节点的未被覆盖距离非负，说明需要额外覆盖点。
参考代码
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1e9;
const int N = 1e5 + 10;
int n, k, t, ans;
vector<int> g[N];
int dp[N][2];
void dfs(int u, int fa)
{
dp[u][0] = -INF;
dp[u][1] = INF;
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] = max(dp[u][0], dp[v][0] + 1);
dp[u][1] = min(dp[u][1], dp[v][1] + 1);
}
if (dp[u][1] > k) dp[u][0] = max(0, dp[u][0]);
if (dp[u][0] + dp[u][1] <= k) dp[u][0] = -INF;
if (dp[u][0] == k) dp[u][0] = -INF, dp[u][1] = 0, ans ++;
}
int main()
{
cin >> n >> k;
for (int i = 1; i < n; i ++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1, -1);
if (dp[1][0] >= 0) ans ++;
cout << ans;
return 0;
}
