P2899 [USACO08JAN]Cell Phone Network G

一个节点能被覆盖，当且仅当一下三种情况：

在该点的父节点设置信号塔；
在该点设置信号塔；
在该点的一个子节点设置信号塔。

用 $f _{x, op}$ ，表示 $x$ 节点对应状态的最少的信号塔数量。

如果一个点的父节点已经有了信号塔，那么这个节点既可以选择要信号塔，也可以选择不要信号塔。

如果一个点要在一个子节点设置信号塔，那么可以让所以子节点随意设置，在依次强制其中一个为信号塔。

查看代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10;
int n, f[N][3];
int idx, hd[N], nxt[M], edg[M];
int dfs(int, int, int);
int cal(int x, bool chs, int fa)
{
    if (chs)
    {
        int res = 1;
        for (int i = hd[x]; ~i; i = nxt[i])
            if (edg[i] != fa)
                res += dfs(edg[i], 0, x);
        return res;
    }
    else
    {
        int res = 0;
        for (int i = hd[x]; ~i; i = nxt[i])
            if (edg[i] != fa)
                res += min(dfs(edg[i], 1, x), dfs(edg[i], 2, x));
        return res;
    }
}
int dfs(int x, int op, int fa)
{
    if (~f[x][op])
        return f[x][op];
    if (op == 0)
        f[x][op] = min(cal(x, 0, fa), cal(x, 1, fa));
    else if (op == 1)
        f[x][op] = cal(x, 1, fa);
    else if (op == 2)
    {
        int s = 0;
        for (int i = hd[x]; ~i; i = nxt[i])
            if (edg[i] != fa)
                s += min(dfs(edg[i], 1, x), dfs(edg[i], 2, x));
        f[x][op] = n;
        for (int i = hd[x]; ~i; i = nxt[i])
            if (edg[i] != fa)
                f[x][op] = min(f[x][op], s - min(dfs(edg[i], 1, x), dfs(edg[i], 2, x)) + dfs(edg[i], 1, x));
    }
    return f[x][op];
}
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1, a, b; i < n; i++)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    memset(f, -1, sizeof f);
    printf("%d", min(dfs(1, 1, 0), dfs(1, 2, 0)));
    return 0;
}