公园（park）

题目描述

$\text{Kefa}$ 想去餐厅庆祝自己的第一份工资。

他家附近有一个特殊的公园。这个公园是一棵有根树，共有 $n$ 个节点，根节点是 $1$，也是 $\text{Kefa}$ 的家。

公园里有些节点上有猫。$\text{Kefa}$ 很怕猫，因此如果从家到某个餐厅的路径上，出现了超过 $m$ 个连续有猫的节点，那么 $\text{Kefa}$ 就不会去这个餐厅。

树中的叶子节点表示餐厅。

请你帮助 $\text{Kefa}$ 统计：有多少个餐厅是他可以去的。

输入格式

第一行包含两个整数 $n,m$，其中 $n$ 表示树的节点数量，$m$ 表示路径上允许出现的最多连续有猫节点数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

其中：

• $a_i=0$ 表示节点 $i$ 上没有猫；
• $a_i=1$ 表示节点 $i$ 上有猫。

接下来 $n-1$ 行，每行包含两个整数 $x_i,y_i$，表示节点 $x_i$ 和节点 $y_i$ 之间有一条边。

保证输入的边构成一棵树。

输出格式

输出一行一个整数，表示 $\text{Kefa}$ 可以到达的餐厅数量。

输入输出样例 #1

输入 #1

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

输出 #1

2

样例解释 #1

这棵树中，根节点是 $1$。

节点 $2,3,4$ 都是叶子节点，因此它们都是餐厅。

从节点 $1$ 到节点 $2$ 的路径为：

其中节点 $1$ 和节点 $2$ 都有猫，连续有猫节点数为 $2$，超过了 $m=1$，所以 $\text{Kefa}$ 不能去节点 $2$。

从节点 $1$ 到节点 $3$ 的路径为：

其中节点 $1$ 有猫，节点 $3$ 没有猫，最多连续有猫节点数为 $1$，没有超过 $m=1$，所以 $\text{Kefa}$ 可以去节点 $3$。

从节点 $1$ 到节点 $4$ 的路径同理，也可以到达。

因此答案为 $2$。

输入输出样例 #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

样例解释 #2

叶子节点为 $4,5,6,7$，它们表示餐厅。

从根节点 $1$ 出发：

• 到节点 $4$ 的路径为 $1 \to 2 \to 4$，节点 $4$ 有猫，但路径上最多连续有猫节点数不超过 $1$，可以到达；
• 到节点 $5$ 的路径为 $1 \to 2 \to 5$，可以到达；
• 到节点 $6$ 的路径为 $1 \to 3 \to 6$，节点 $1$ 和节点 $3$ 都有猫，连续有猫节点数超过 $1$，不能到达；
• 到节点 $7$ 的路径为 $1 \to 3 \to 7$，同样不能到达。

所以答案为 $2$。

数据范围与约定

对于所有测试数据，保证：

输入的 $n-1$ 条边保证构成一棵树。

特殊性质 $\text{A}$：保证这棵树是一条链。

特殊性质 $\text{B}$：保证所有节点都没有猫。

特殊性质 $\text{C}$：保证所有节点都有猫。