[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比较好的练手题吧

考虑从子树往上推

$f[i][0/1]$表示以$i$为根的子树，$i$为黑/白的最大值

就只需要枚举每个子树的黑 / 白色转移方程就是了

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    char ch=getchar();
    int res=0;
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
const int N=5050;
const int M=20050;
int n,m,a[N],adj[M],nxt[M],to[M],cnt,in[M],f[M][2];
inline void addedge(int u,int v){
    nxt[++cnt]=adj[u],adj[u]=cnt,to[cnt]=v;
}
inline void dfs(int u,int fa){
    if(in[u]==1&&fa){
        f[u][a[u]]=1,f[u][a[u]^1]=1e8;return;
    }
    f[u][0]=f[u][1]=1;
    for(int e=adj[u];e;e=nxt[e]){
        int v=to[e];
        if(v==fa)continue;
        dfs(v,u);
        f[u][1]+=min(f[v][1]-1,f[v][0]);
        f[u][0]+=min(f[v][1],f[v][0]-1);
    }
}
int main(){
    m=read(),n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<m;i++){
        int u=read(),v=read();
        addedge(u,v),addedge(v,u);
        in[u]++,in[v]++;
    }
    dfs(n+1,0);
    cout<<min(f[n+1][0],f[n+1][1]);
}