题目描述

Kefa 决定用他的第一份大薪水去餐厅庆祝。

他住在一个特别的公园旁。这个公园是一个以 $1$ 号顶点为根的有根树，共有 $n$ 个顶点。顶点 $1$ 也是 Kefa 的家。不幸的是，公园里还有一些猫。Kefa 已经知道哪些顶点有猫。

公园的叶子结点上有餐厅。Kefa 希望选择一家餐厅，但是他非常怕猫，所以如果从餐厅到他家的路径中有超过 $m$ 个连续有猫的顶点，他是绝对不会去这家餐厅的。

你的任务是帮助 Kefa 统计他可以去的餐厅数量。

输入格式

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^{5}$，$1 \leq m \leq n$），分别表示树的顶点数以及 Kefa 能接受的连续有猫顶点的最大数量。

第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$，其中 $a_{i}$ 为 $0$ 表示第 $i$ 个顶点没有猫，$1$ 表示第 $i$ 个顶点有猫。

接下来的 $n-1$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$（$1 \leq x_{i}, y_{i} \leq n$，$x_{i} \ne y_{i}$），表示树中连接顶点 $x_{i}$ 和 $y_{i}$ 的一条边。

保证给定的边集构成一棵树。

输出格式

输出一个整数，表示从 Kefa 家到满足条件（路径上连续有猫顶点数不超过 $m$）的叶子节点（即餐厅）的数量。

说明/提示

我们提醒你，树是一个有 $n$ 个顶点、$n-1$ 条边且连通无环的图。有根树是选定一个顶点作为根结点的树。在一条边连接的两个顶点中，一个更靠近根的为父节点，另一个为子节点。一个没有子节点的顶点被称为叶子节点。

样例一说明： 红色为含有猫的顶点。餐厅在顶点 $2,3,4$。Kefa 不能去顶点 $2$ 的餐厅。

样例二说明： 餐厅在顶点 $4,5,6,7$。Kefa 不能去顶点 $6,7$ 的餐厅。

由 ChatGPT 5 翻译

样例

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

2

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

2