Kefa决定去餐厅庆祝他的第一份高薪。
他住在一个不寻常的公园旁边。该公园是一棵由 n 个顶点组成的有根树,根位于顶点 1。顶点 1 还包含 Kefa 的房子。对于我们的英雄来说不幸的是,公园里也有猫。 Kefa 已经找出了哪些顶点中有猫。
公园的叶顶点包含餐馆。 Kefa 想要选择一家他要去的餐厅,但不幸的是,他非常害怕猫,所以如果从餐厅到他家的路径包含超过 m 个连续的有猫的顶点,他就不可能去该餐厅。
你的任务是帮助Kefa数一下他可以去的餐厅数量。
输入
第一行包含两个整数,n 和 m (2 ≤ n ≤ 105, 1 ≤ m ≤ n) — 树的顶点数以及对于 Kefa 来说仍然可以的有猫的连续顶点的最大数量。
第二行包含 n 个整数 a1, a2, ..., an,其中每个 ai 要么等于 0(则顶点 i 没有猫),要么等于 1(则顶点 i 有猫)。
接下来的 n - 1 行包含树的边,格式为“xi yi”(不带引号)(1 ≤ xi, yi ≤ n, xi ≠ yi),其中 xi 和 yi 是树的顶点,通过边连接。
保证给定的边集指定一棵树。
输出
单个整数 — 从 Kefa 家到该路径的树的不同叶子的数量,最多包含 m 个有猫的连续顶点。
示例
输入 #1
4 1 1 1 0 0 1 2 1 3 1 4
输出 #1
2
输入 #2
7 1 1 0 1 1 0 0 0 1 2 1 3 2 4 2 5 3 6 3 7
输出 #2
2
注意
让我们提醒您,树是一个有 n 个顶点和 n - 1 条边的连通图。有根树是具有称为根的特殊顶点的树。在由边连接的任意两个顶点之间的有根树中,一个顶点是父顶点(靠近根的顶点),另一个顶点是子顶点。如果一个顶点没有子节点,则该顶点称为叶子。
第一个样本测试注意事项:包含猫的顶点标记为红色。餐厅位于顶点 2、3、4。Kefa 不能只去位于顶点 2 的餐厅。
第二个样本测试注意事项:餐厅位于顶点 4、5、6、7。Kefa 不能去餐厅 6、7。