题意:
给出由n个点和(n-1)条边构成的树,每个点可以覆盖每个相邻点,求把树上所有点覆盖完成至少需要挑出多少点来做覆盖操作
思路:
先明确用树形dp来做解答,用dp[i][]来表示覆盖对应点和其下方所有节点的最小花费
对于要覆盖的每个点,我们可以有三种选择:
1.自己覆盖自己:这时字节点的选择任意,选其中最小的即可
2.由父亲节点来覆盖自己:这时所有子节点不得选择同样的操作
3.由子节点来覆盖自己:这是相对校麻烦,我们可以先让它所有子节点选择由子节点的子节点来覆盖,再挑出1个或以上的子节点改由自己覆盖自己
代码如下:
#include <bits/stdc++.h>
#include<vector>
using namespace std;
const int N = 1e4 + 5;
int x, y, vist[N], dp[N][3];
vector<int>son[N];
void dfs(int k) {
vist[k] = 1;
dp[k][1] = 1;
int n = son[k].size(), x,y=0;
//如果是叶子节点
if (n==1&&k!=1)dp[k][0] = 1;
int a[N], num = 0;
for (int i = 0; i < n; i++) {
int u = son[k][i];
if (vist[u])continue;
dfs(u);
int t = min(dp[u][0], dp[u][1]);
//自己覆盖自己
dp[k][1] += min(t,dp[u][2]);
//借由父节点覆盖自己
dp[k][2] += t;
//由子节点覆盖自己
dp[k][0] += dp[u][0];
//用数组存储子节点两种选择的差值
a[num++] = dp[u][1] - dp[u][0];
}
if (num == 0)return;
sort(a, a + num);
//第一个子节点必须转为自己覆盖自己
dp[k][0] += a[0];
//之后的子节点两种选择选较小
for (int i = 1; i < num && a[i] < 0; i++)dp[k][0] += a[i];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 1; i < n; i++) {
cin >> x >> y;
son[x].push_back(y);
son[y].push_back(x);
}
dfs(1);
cout << min(dp[1][0], dp[1][1]) << endl;
return 0;
}