Preface

随机跳题做到了这道。

题目

https://www.luogu.com.cn/problem/P2899

题解

其实就是交叉染色。我们考虑每棵子树的情况。设 $f[u]$ 表示以 $u$ 为根的最小答案。三种子情况：

• $f[u][0]$: $u$ 自己本身被染色
• $f[u][1]$: $u$ 的某个儿子染色了，使之被覆盖进了范围
• $f[u][2]$: $u$ 的父亲染色了，使之被覆盖进了范围

接下来是转移方程：

$$
f[u][0] = 1 + \sum_{v \in u.son} \min \{f[v][0], f[v][1], f[v][2]\}
$$

$$
f[u][1] = \min_{x\in u.son} \left(f[x][0] + \sum_{v \in u.son \backslash \{x\}} \min\{f[v][0], f[v][1]\}\right)
$$

$$
f[u][2] = \sum_{v\in u.son} \min \{f[v][0], f[v][1]\}
$$

我们会发现如果上暴力的话，第二个转移方程的复杂度是 $O(n^2)$，我们不妨简单地优化一下。第二个方程的主要含义是枚举哪个儿子必须要被染色，使之覆盖到父亲。那么很简单，假设如果那个染色的儿子是 $x$，然而却有一个更好的儿子 $y$ 使得代价更小，那么必然有：

$$
f[x][0] + \sum_{v \in u.son \backslash \{x\}} \min\{f[v][0], f[v][1]\} > f[y][0] + \sum_{v \in u.son \backslash \{y\}} \min\{f[v][0], f[v][1]\}
$$

化简一下：

$$
f[x][0] - \min \{f[x][0], f[x][1]\} > f[y][0] - \min \{f[y][0], f[y][1]\}
$$

这个复杂度是 $O(n)$

代码

#include <iostream>

using namespace std;

const int maxn = 2e4+5;

// [u][0] -> u
// [u][1] -> son
// [u][2] -> fa
int n, head[maxn], f[maxn][3], ecnt = 2;
struct edge { int to, next; } g[maxn];

void add_edge(int u, int v) {
    g[ecnt] = (edge) {v, head[u]};
    head[u] = ecnt ++;
}

void dfs(int u, int fa) {
    f[u][0] = 1;
    int x = 0;
    for (int e = head[u]; e; e = g[e].next) {
        int v = g[e].to;
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += min(min(f[v][0], f[v][1]), f[v][2]);
        f[u][2] += min(f[v][0], f[v][1]);
        if (f[x][0] - min(f[x][0], f[x][1]) > f[v][0] - min(f[v][0], f[v][1]))
            x = v;
    }
    f[u][1] = f[x][0];
    for (int e = head[u]; e; e = g[e].next) {
        int v = g[e].to;
        if (v == fa) continue;
        if (v == x) continue;
        f[u][1] += min(f[v][0], f[v][1]);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i ++) {
        int u, v; cin >> u >> v;
        add_edge(u, v); add_edge(v, u);
    }
    f[0][0] = 2e9;
    dfs(1, 0);
    cout << min(f[1][0], f[1][1]) << endl;
    return 0;
}