P2014【CQOI2009】叶子的颜色 | |
|
问题描述
给一棵$m$个节点的无根树,你可以选择一个度数大于$1$的节点作为根,然后给一些节点(根、内部节点和叶子均可)着以黑色或白色。你的着色方案应该保证根节点到每个叶子的简单路径上都至少包含一个有色节点(哪怕是这个叶子本身)。
对于每个叶节点$u$,定义$c[u]$为从根到$u$节点的简单路径上最后一个有色节点的颜色,即$u$的有色祖先中离$u$最近的一个节点的颜色。给出每个$c[u]$的值,设计着色方案,使得着色节点的个数尽量少。
输入格式
第一行包含两个正整数$m,n$,其中$n$是叶子的个数,$m$是节点总数。节点编号为$1,2,\dots,m$,其中编号$1,2,\dots,n$是叶子。
以下$n$行每行一个$0$或$1$的整数($0$表示黑色,$1$表示白色),依次为$c[1],c[2],\dots,c[n]$。
以下$m-1$行每行两个整数$a,b(1\leq a<b\leq m)$,表示节点$a$和$b$有边相连。
输出格式
仅一个数,即着色节点数的最小值。
样例输入
5 3
0
1
0
1 4
2 5
4 5
3 5
样例输出
2
提示
【数据规模】
测试数据 | \(\qquad\) | \(m\) | \(\qquad\) | \(n\) |
---|---|---|---|---|
1 | 10 | 5 | ||
2 | 50 | 23 | ||
3 | 100 | 50 | ||
4 | 200 | 98 | ||
5 | 400 | 197 | ||
6 | 1000 | 498 | ||
7 | 4000 | 2044 | ||
8 | 8000 | 4004 | ||
9 | 10000 | 5021 | ||
10 | 10000 | 4996 |