1304: [CQOI2009]叶子的染色

题意：

给你一棵$m$个节点的树，你要给其中一些节点染成黑色或白色，并定一个根，使得它每个叶子节点$i$都满足它到根的路径上第一个有颜色的点的颜色是$c_i$。给定$c$，最小化染色的节点个数。

题解：

树形DP
一开始想着换根，觉得非常难写，写了第一个dfs就弃疗了。。。看了发题解，发现其实哪个点做根是一样的（除了叶子）。状态就是$f_{i, 0/1/2}$表示$i$的子树，需要一个0颜色/需要一个1颜色/不需要颜色。随便转移。

代码：

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

const int inf = 0x3f3f3f3f;
int n, m, c[5100], num = 0, fst[10010], f[10010][3]; // x的子树，需要一个0/1/不需要
struct edge
{
    int x, y, n;
} e[20010];
int ans = inf;

void ins(int x, int y)
{
    e[++num] = {x, y, fst[x]};
    fst[x] = num;
}
void dfs1(int x, int fa)
{
    for (int i = fst[x]; i; i = e[i].n)
    {
        int y = e[i].y;
        if (y == fa) continue;
        dfs1(y, x);
        f[x][0] += min(f[y][0], min(f[y][1] + 1, f[y][2]));
        f[x][1] += min(f[y][1], min(f[y][0] + 1, f[y][2]));
    }
    if (x <= n)
    {
        f[x][c[x]] = 0;
        f[x][c[x] ^ 1] = inf;
        f[x][2] = 1;
    }
    else
        f[x][2] = min(f[x][0], f[x][1]) + 1;
}
int main()
{
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    for (int i = 1; i < m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ins(x, y);
        ins(y, x);
    }
    if (n == 1)
    {
        puts("1");
        return 0;
    }
    if (n == 2)
    {
        printf("%d\n", 1 + (c[1] != c[2]));
        return 0;
    }
    dfs1(n + 1, 0);/*
    for (int i = 1; i <= m; i++)
        printf("%d %d %d\n", f[i][0], f[i][1], f[i][2]);*/
    printf("%d\n", f[n + 1][2]);
}