#CF580C. 公园餐厅
公园餐厅
题目描述
给定一棵有 个顶点的树,以顶点 为根。顶点 是否有猫由 表示, 表示有猫, 表示没有猫。
没有子节点的顶点称为叶子,每个叶子处有一家餐馆。从根到一家餐馆的唯一路径上,如果曾出现超过 个连续有猫的顶点,这家餐馆就不能前往。没有猫的顶点会中断连续段。
请统计可以前往的餐馆数量。根节点本身不属于餐馆。
输入格式
第一行输入两个整数 $n,k\left(2\leqq n\leqq10^5;\ 1\leqq k\leqq n\right)$,分别代表顶点数量和允许的最大连续猫数。
第二行输入 个整数 。
此后 行,每行输入两个整数 $u_i,v_i\left(1\leqq u_i,v_i\leqq n;\ u_i\neq v_i\right)$。保证这些边构成一棵树。
输出格式
输出一个整数,代表合法餐馆数量。
测试样例
4 1
1 1 0 0
1 2
1 3
1 4
2
样例 1 解释
叶子为顶点 。根到顶点 的路径上连续有猫的顶点数为 ,超过限制 ;到顶点 或 的路径最多只有一个连续有猫顶点,因此答案为 。
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
2