#CF580C. 公园餐厅

公园餐厅

题目描述

\hspace{15pt}给定一棵有 nn 个顶点的树,以顶点 11 为根。顶点 ii 是否有猫由 aia_i 表示,ai=1a_i=1 表示有猫,ai=0a_i=0 表示没有猫。

\hspace{15pt}没有子节点的顶点称为叶子,每个叶子处有一家餐馆。从根到一家餐馆的唯一路径上,如果曾出现超过 kk 个连续有猫的顶点,这家餐馆就不能前往。没有猫的顶点会中断连续段。

\hspace{15pt}请统计可以前往的餐馆数量。根节点本身不属于餐馆。

输入格式

\hspace{15pt}第一行输入两个整数 $n,k\left(2\leqq n\leqq10^5;\ 1\leqq k\leqq n\right)$,分别代表顶点数量和允许的最大连续猫数。

\hspace{15pt}第二行输入 nn 个整数 a1,a2,…,an(0≦ai≦1)a_1,a_2,\dots,a_n\left(0\leqq a_i\leqq1\right)。

\hspace{15pt}此后 n−1n-1 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$。保证这些边构成一棵树。

输出格式

\hspace{15pt}输出一个整数,代表合法餐馆数量。

测试样例

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

样例 1 解释

\hspace{15pt}叶子为顶点 2,3,42,3,4。根到顶点 22 的路径上连续有猫的顶点数为 22,超过限制 11;到顶点 33 或 44 的路径最多只有一个连续有猫顶点,因此答案为 22。

7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
2