Description：

给一棵树，告诉你哪些节点是叶子，并给定每个叶子到根路径上最深一个染色点的颜色，最小化染色的点的个数。

$1\leqslant n\leqslant 10000$

Solution：

设 $f[i][0/1/2]$ 表示状态， $f[i][0]$ 表示子树内所有颜色为 $1$ 的叶子都已经有点处理他，还有一些 $0$ 的叶子需要上面去覆盖他，这个情况下子树内最小已经放了多少个点， $f[i][1]$ 相反， $f[i][2]$ 表示这棵子树已经全部处理完了。

对于一个叶子，不妨设它的颜色为 $0$ ，那么 $f[k][0]=0,f[k][1]=\infty,f[k][2]=1$ ，转移为： $$ f[k][0]+=\min(f[e[i].to][0],f[e[i].to][1]+1,f[e[i].to][2])\\ f[k][1]+=\min(f[e[i].to][1],f[e[i].to][0]+1,f[e[i].to][2])\\ f[k][2]+=\min(\min(f[e[i].to][1],f[e[i].to][0])+1,f[e[i].to][2]) $$ 也就是说在这个点染色是在他的父节点上决定的，最后枚举根染什么颜色，答案就是： $$ ans=\min(f[n + 1][2],\min(f[n + 1][0],f[n + 1][1]) + 1) $$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int m,n;

#define MAXN 10010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int val[MAXN];

int f[MAXN][3];

bool v[MAXN];

#define INF 0x3f3f3f3f

void dp(int k)

{

	v[k] = true;

	if(k <= n)

	{

		f[k][val[k]] = 0;

		f[k][val[k] ^ 1] = INF;

		f[k][2] = 1;

		return;

	}

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(v[e[i].to])continue;

		dp(e[i].to);

		f[k][0] += min(f[e[i].to][1] + 1,min(f[e[i].to][0],f[e[i].to][2]));

		f[k][1] += min(f[e[i].to][0] + 1,min(f[e[i].to][1],f[e[i].to][2]));

		f[k][2] += min(f[e[i].to][2],min(f[e[i].to][0],f[e[i].to][1]) + 1);

	}

	return;

}

int main()

{

	scanf("%d%d",&m,&n);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	int a,b;

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

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dp(n + 1);

	cout << min(f[n + 1][2],min(f[n + 1][0],f[n + 1][1]) + 1) << endl;

	return 0;

}