TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2014
  • 题目
  • P2014【CQOI2009】叶子的颜色
    限制 : 时间限制 : 20000 MS   空间限制 : 524288 KB
    问题描述

    给一棵$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