题目背景

由于评测机性能差异，添加了额外 1.5 秒的时限。

题目描述

JOI 君居住的 IOI 王国有 $N$ 座城镇，编号从 $1$ 到 $N$。此外，IOI 王国有 $N-1$ 条道路，编号从 $1$ 到 $N-1$。道路 $j$ ($1 \leq j \leq N-1$) 双向连接城镇 $U_j$ 和城镇 $V_j$。通过使用若干条道路，可以从任何城镇前往任何其他城镇。

现在 IOI 王国将举办一场盖章拉力赛。每座城镇都将设置一个盖章站。城镇 $i$ ($1 \leq i \leq N$) 的盖章站将在时间 $T_i$ 设置。

JOI 君决定参加这场盖章拉力赛。在时间 $0$，JOI 君从其中一座城镇出发。此外，JOI 君在时间 $0$ 拥有耐力值 $D$。

当 JOI 君在时间 $t$ 位于城镇 $i$ 时，他采取以下行动：

1. 首先，如果当前城镇已经设置了盖章站，他就盖章。也就是说，如果 $T_i \leq t$，他就盖章。

2. 接下来，他选择结束盖章拉力赛或移动到另一座城镇。然而，只有当存在通过道路与城镇 $i$ 相连且他尚未访问过的相邻城镇，并且他当前的耐力值至少为 $1$ 时，他才能选择移动到另一座城镇。

3. 如果 JOI 君选择移动到另一座城镇，他会在与城镇 $i$ 相连的城镇中选择一座未访问过的城镇 $j$ 并移动到那里。他的耐力值减少 $1$，并于时间 $t + 1$ 到达城镇 $j$。

4. 如果 JOI 君选择结束盖章拉力赛，若到那时为止他已经盖了至少一次章，则拉力赛成功，他可以在那里领取一份礼物。否则，拉力赛失败。

假设除城镇间的旅行时间外，所有其他时间都忽略不计。请注意，JOI 君不能留在同一座城镇。

你是活动组织者。如果 JOI 君在盖章拉力赛中取得成功，你需要在相应的城镇准备礼物。然而，礼物的数量是有限的，所以你想在尽可能少的城镇准备礼物。不幸的是，你不知道 JOI 君会从哪座城镇出发。因此，对于每个 $s$ ($1 \leq s \leq N$)，你想找出当 JOI 君从城镇 $s$ 出发时，必须准备礼物的城镇数量。换句话说，你需要统计满足以下条件的 $g$ ($1 \leq g \leq N$) 的数量：当 JOI 君在城镇 $g$ 结束时，盖章拉力赛有可能成功。

给定关于 IOI 王国城镇和道路的信息、JOI 君的耐力值以及盖章站的设置时间，编写一个程序，对于每座城镇，计算当 JOI 君从该城镇出发时必须准备礼物的城镇数量。

输入格式

从标准输入读取以下数据：

$N$ $D$
$T_1$ $T_2$ $\cdots$ $T_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

输出格式

输出 $N$ 行到标准输出。第 $s$ 行 ($1 \leq s \leq N$) 应包含当 JOI 君从城镇 $s$ 出发时必须准备礼物的城镇数量。

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

2
3
4
2
2

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

2
1
2
0
1

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

2
2
7
5
1
2
5

提示

样例 1

我们展示一个当 $s = 1$ 时 JOI 君行动的例子。

• 在时间 $0$，JOI 君在城镇 $1$ 并采取以下行动。
  • 城镇 $1$ 的盖章站尚未设置，所以 JOI 君没有盖章。
  • JOI 君当前的耐力值是 $2$。他移动到城镇 $2$，这是通过道路与城镇 $1$ 相连的未访问城镇之一。
  • JOI 君的耐力值减少 $1$，并于时间 $1$ 到达城镇 $2$。
• 在时间 $1$，JOI 君在城镇 $2$ 并采取以下行动。
  • 城镇 $2$ 的盖章站尚未设置，所以 JOI 君没有盖章。
  • JOI 君当前的耐力值是 $1$。他移动到城镇 $3$，这是通过道路与城镇 $2$ 相连的未访问城镇之一。
  • JOI 君的耐力值减少 $1$，并于时间 $2$ 到达城镇 $3$。
• 在时间 $2$，JOI 君在城镇 $3$ 并采取以下行动。
  • 城镇 $3$ 的盖章站已经设置，所以 JOI 君盖章。
  • JOI 君选择在这里结束盖章拉力赛。由于他已经盖了至少一次章，盖章拉力赛成功。他收到一份礼物。

因此，当 JOI 君从城镇 $1$ 出发并在城镇 $3$ 结束盖章拉力赛时，盖章拉力赛可以成功，因此有必要在城镇 $3$ 准备礼物。当 JOI 君从城镇 $1$ 出发时，仅需在城镇 $3$ 和 $4$ 准备礼物，因此输出的第一行应为 $2$。

此外，当 JOI 君从城镇 $2$ 出发时，仅需在城镇 $3, 4$ 和 $5$ 准备礼物，因此输出的第二行应为 $3$。

该输入样例满足子任务 $3, 6$ 的限制。

样例 2

该输入样例满足子任务 $1, 2, 3, 4, 6$ 的限制。

样例 3

该输入样例满足子任务 $3, 5, 6$ 的限制。

限制

• $2 \leq N \leq 400\,000$。
• $0 \leq D \leq N-1$。
• $0 \leq T_i \leq N$ ($1 \leq i \leq N$)。
• $1 \leq U_j < V_j \leq N$ ($1 \leq j \leq N-1$)。
• 通过使用若干条道路，可以从任何城镇前往任何其他城镇。
• 给定的值均为整数。

子任务

1. (3 分) $D \leq 1$。
2. (7 分) $N \leq 3\,000, (U_j, V_j) = (j, j+1)$ ($1 \leq j \leq N-1$)。
3. (10 分) $N \leq 3\,000$。
4. (11 分) $(U_j, V_j) = (j, j+1)$ ($1 \leq j \leq N-1$)。
5. (41 分) $D = N-1, N \leq 150\,000$。
6. (28 分) 无额外限制。