Eva

Time Limit: 10 Sec  Memory Limit: 162 MB
Description

给一棵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 有边相连。

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

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

2

M<=10000

N<=5021

/**************************************************************

    Problem: 1304

    User: ictsing

    Language: C++

    Result: Accepted

    Time:40 ms

    Memory:1796 kb

****************************************************************/

 

//BZOJ1304 [CQOI2009]叶子的染色

#include <iostream>

#include <cstdio>

using namespace std;

const int mt = 10000+5 ;

const int inf =100000;

int vis[mt],c[mt],f[mt][2];

int ecnt=0;

int to[mt<<2],nxt[mt<<2],adj[mt];

int n,m;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void adde(int u,int v)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],adj[u]=ecnt;

}

void dfs(int u)

{

    vis[u]=1;

    if(u<=m) {f[u][c[u]]=1,f[u][c[u]^1]=inf;return ;}

    else f[u][0]=f[u][1]=1;

    for(int i=adj[u];i;i=nxt[i])

    {

        int v=to[i];

        if(vis[v]) continue;

        dfs(v);

        f[u][0]+=min(f[v][1],f[v][0]-1);

        f[u][1]+=min(f[v][1]-1,f[v][0]);

    }

}

int main()

{

    n=read(),m=read();

    for(int i=1;i<=m;i++) c[i]=read();

    for(int i=1;i<n;i++)

    {

        int x=read(),y=read();

        adde(x,y),adde(y,x);

    }

    dfs(n);

    printf("%d\n",min(f[n][0],f[n][1]));

    return 0;

}