题目地址：洛谷：【P3155】[CQOI2009]叶子的染色 – 洛谷、BZOJ：Problem 1304. — [CQOI2009]叶子的染色

题目描述

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。 对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

输入输出格式

输入格式：
第一行包含两个正整数m, n，其中n是叶子的个数，m是结点总数。结点编号为1，2，…，m，其中编号1，2，… ，n是叶子。以下n行每行一个0或1的整数（0表示黑色，1表示白色），依次为c[1]，c[2]，…，c[n]。以下m-1行每行两个整数a，b（1<=a < b <= m），表示结点a和b 有边相连。

输出格式：
仅一个数，即着色结点数的最小值。

输入输出样例

输入样例#1：

5 3
0
1
0
1 4
2 5
4 5
3 5

输出样例#1：

2

说明

M<=10000
N<=5021

题解

树形DP的模型。令dp[u][col]表示以u为根的子树，希望的最后一个节点为col的情况子树中最少染色数。转移方程如下。
dp[u][col] = \sum \min\{dp[v][col], dp[v][!col] + 1\}
其中v是u的儿子。
这个转移的含义是，如果儿子的要求与自己的要求一样，那么这个转移过程中不需要再染色。如果要求不一样，则把儿子染上色，再考虑根的事情。初始把每个叶子节点的c[u]颜色设为0，非c[u]颜色设为无穷大，转移上来即可。
如果我们枚举每个点是根的可能性，那么这个DP是O(n^2)的，数据范围承受不了。但是我们思考两个相邻点一个为根或另一个为根的情况，相邻点绝对不可能同色，那么情况只剩下一个染一个不染或者异色，两者为根并不会改变答案。可以假设我们已经得到了最优解，然后尝试把根的一个儿子拎上来这样理解。那么就证明了任意非叶子为根答案一样，任意指定一个非叶子节点为根即可。复杂度优化为O(n)。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm> 
#include <vector>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

// variables

const int MAXN = 10005, INF = 1e9;

std::vector<int> gra[MAXN];

int m, n, c[MAXN], dp[MAXN][2], ut, vt;

// dfs

inline void dfs(int fa, int u) {
    if(u <= n) {
        dp[u][c[u]] = 0;
        dp[u][c[u] ^ 1] = INF;
        return;
    }
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == fa) continue;
        dfs(u, v);
        dp[u][0] += std::min(dp[v][0], dp[v][1] + 1);
        dp[u][1] += std::min(dp[v][1], dp[v][0] + 1);
    }
}

int main() {
    m = readint();
    n = readint();
    for(int i = 1; i <= n; i++) {
        c[i] = readint();
    }
    for(int i = 1; i < m; i++) {
        ut = readint();
        vt = readint();
        gra[ut].push_back(vt);
        gra[vt].push_back(ut);
    }
    dfs(0, m);
    printf("%d", std::min(dp[m][0], dp[m][1]) + 1);
    return 0;
}