题目描述

给定一棵包含 n 个结点的树，其中每个结点均被唯一地编号 1∼n。树的根结点编号为 1。

这些结点都被随机地染上了黑色或者白色的颜色。

现给定一个描述叶子结点的概念——美与丑：从某个叶子结点出发，沿着到根结点的路径行进（包括起始和终止的结点），途中如果出现连续排列的黑色结点数量超过 m 个，则称该叶子结点为 丑陋的 叶子结点，否则称为 美丽的 叶子结点。

请你编写一个程序，统计给定树中美丽的叶子结点的数量，并输出结果。

输入格式

第一行包含两个整数 n,m。

第二行包含 n 个整数 a1​,a2​,...,an​，其中 ai​ 表示第 i 个结点的颜色，1 表示黑色，0 表示白色。

接下来 n−1 行，每行包含两个整数 x,y，表示结点 x 和结点 y 之间存在一条无向边。

保证输入给定的是一棵树。

输出格式

一个整数，表示给定树中 美丽的 叶子结点的数量。

样例

输入数据#1

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

Copy

输出数据#1

2

Copy

输入数据#2

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

Copy

输出数据#2

2

Copy

数据范围

• 前 20% 的测试点满足：m=1。
• 前 40% 的测试点满足 2≤n≤10000。
• 另有 10% 的测试点满足：每行输入的 x,y 满足 x=y−1。
• 另有 10% 的测试点满足：ai​=1 恒成立。
• 对于所有测试点，满足 2≤n≤2×105，1≤m≤n，0≤ai​≤1，1≤x,y≤n，x≠y。