CQOI2009 叶子的颜色

题目大意：https://www.cnblogs.com/xxzh/p/9278487.html
代码：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000 + 10;
const int inf = 1e9 + 7;
int m, n, k = 1;
int head[maxn], c[maxn], dp[maxn][2];
struct EDGE {
    int to, next;
} e[maxn];
void add(int u, int v) {
    e[++k].next = head[u];
    e[k].to = v;
    head[u] = k;
}
void dfs(int x, int fa) {
    if (x <= n) {
        dp[x][c[x]] = 1;
        dp[x][c[x] ^ 1] = inf;
        return;
    }
    dp[x][1] = dp[x][0] = 1;
    for (int i = head[x]; i; i = e[i].next) {
        if (e[i].to == fa)
            continue;
        dfs(e[i].to, x);
        dp[x][1] += min(dp[e[i].to][1] - 1, dp[e[i].to][0]);
        dp[x][0] += min(dp[e[i].to][1], dp[e[i].to][0] - 1);
    }
}
int main() {
    int ans;
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int i = 1; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    dfs(n + 1, 0);
    ans = min(dp[n + 1][0], dp[n + 1][1]);
    printf("%d\n", ans);
}