「Bzoj 1304」「CQOI2009」叶子的染色 (树形DP)

BZOJ 1304
题意：见上。

显然随意找一个不是叶子的点当根即可。
设$dp(u, 0/1/2)$为$u$点填$0,1$色，不填($2$)的满足最小值。
然后转移即可。具体看代码。

怎么那么水的 DP 我没想出来……

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 10000 + 5, ZINF = 2000000000;

    struct edge {int v, nxt; } ed[MAXN * 2];

    int m, n, c[MAXN], dp[MAXN][3], en, hd[MAXN];

    void ins(int u, int v) {ed[++en] = (edge){v, hd[u]}, hd[u] = en;}

    void dfs(int u, int fa) {
        if (u <= n) {
            dp[u][c[u]] = 1, dp[u][2] = dp[u][c[u] ^ 1] = ZINF;
            return ;
        } else dp[u][1] = 1, dp[u][0] = 1, dp[u][2] = 0;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                dfs(e.v, u);
                dp[u][0] += min(dp[e.v][0] - 1, dp[e.v][1]);
                dp[u][1] += min(dp[e.v][1] - 1, dp[e.v][0]);
                dp[u][2] += min(min(dp[e.v][0], dp[e.v][1]), dp[e.v][2]);
            }
        }
    }

    void clean() {
        en = 0, ms(hd, -1);
    }
    int solve() {
        scanf("%d%d", &m, &n);
        if (m == 1) return printf("1\n"), 0;
        for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
        clean();
        for (int u, v, i = 1; i < m; ++i) scanf("%d%d", &u, &v), ins(u, v), ins(v, u);
        dfs(n + 1, 0);
        //cerr << "???" << dp[n + 1][0] << " " << dp[n + 1][1] << " " << dp[n + 1][2] << endl;
        printf("%d\n", min(min(dp[n + 1][0], dp[n + 1][1]), dp[n + 1][2]));
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}