洛谷3155 [CQOI2009]叶子的染色

题意

一棵无根树，要求根节点到每个叶子的路径上都至少有一个有色节点。

给出根节点到每个叶子节点路径上最后一个有色节点的颜色，求有色节点个数最小值。

其中点数 $N\le 1000$ ，叶子节点个数 $M\le 5021$ 。（我按个人习惯反过来了）

题解

树形dp，用 $f[x][0/1]$ 表示以 $x$ 为根的子树，最后一个有色节点颜色为黑/白的最优情况。

考虑状态转移，如果子节点和自己要求一样，则节点个数不变；如果不一样，就意味着子节点染了自己要求的颜色，节点个数 $+1$ 。得到方程：

$$f[x][i] = \Sigma min(f[y][i],f[y][!i]+1)$$

虽然是无根树，但取哪个为根对答案没有影响（我也不知道怎么证明），所以可以将前 $M$ 个节点设为叶子节点，以 $M+1$ 为根搜索。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

struct Edge {
    int next,to;
} edge[20005];
bool s[10005];
int cnt,head[10005],n,m,a,b,f[10005][2];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int x,int fa)
{
    if (x<=m)
    {
        f[x][s[x]]=0;
        f[x][s[x]^1]=1e9;
    }
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==fa) continue;
        dfs(y,x);
        f[x][0]+=min(f[y][1]+1,f[y][0]);
        f[x][1]+=min(f[y][0]+1,f[y][1]);
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=m;i++) s[i]=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    dfs(m+1,0);
    printf("%d",min(f[m+1][0],f[m+1][1])+1);
    return 0;
}