[USACO08JAN]Cell Phone Network G

题意:

给出由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;
}