题目描述

Description

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。 对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

Input

第一行包含两个正整数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 有边相连。

Output

仅一个数，即着色结点数的最小值。

Sample Input

5 3
0
1
0
1 4
2 5
4 5
3 5

Sample Output

2

HINT

M<=10000 N<=5021

题目分析

树形DP
f[i][j]表示i这个节点染成j色后，以它为根的子树满足要求，需要染多少个点

尽管这题n^2能过 这题貌似随便选一个非叶子节点答案是一样的
并且好像有贪心做法??

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,ans=0x3f3f3f3f;
int tot,head[10010],to[20010],net[20010],a[20010],f[10010][3];
void add(int x,int y) { net[++tot]=head[x],head[x]=tot,to[tot]=y; }
void dfs(int x,int temp)
{
    if(x<=m)
    {
        f[x][a[x]]=0,f[x][a[x]^1]=0x3f3f3f3f;
        return ;
    }
    for(int i=head[x];i;i=net[i])
        if(to[i]!=temp)
        {
            dfs(to[i],x);
            f[x][0]+=min(f[to[i]][1]+1,f[to[i]][0]);
            f[x][1]+=min(f[to[i]][0]+1,f[to[i]][1]);
        }
}
int main()
{   
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&a[i]);
    for(int x,y,i=1;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    for(int i=n;i<=n;i++) 
        memset(f,0,sizeof f),dfs(i,0),ans=min(ans,min(f[i][1],f[i][0])+1);
    printf("%d",ans);
    return 0;
}