分数: 100 点
问题陈述
有 N JOI君居住的IOI国的城镇,编号为 1 to N。 另外,还有 N-1 IOI 国家的道路,编号为 1 to 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君的体力也有 D 时间 0.
当JOI君在城里时 i 时间 t,他采取以下行动。
- 首先,如果当前城镇已经安装了印章站,他就按下印章。 也就是说,如果 T_i \leq t.
- 接下来,他选择完成集邮活动或搬到另一个城镇。 然而,只有当存在与城镇相连的相邻城镇时,他才能选择搬到另一个城镇 i 经过一条他还没有去过的路,他目前的体力至少是 1.
- 如果JOI君选择搬到另一个城镇,他会选择一个未去过的城镇 j 与城镇相连的城镇之间 i 在一条路边,然后移动到那里。 他的体力下降了 1,他到达城镇 j 时间 t+1.
- 如果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-kun 从城镇出发时必须准备礼物的城镇数量 s.
约束
- 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).
- 可以使用一定数量的道路从任何城镇前往任何其他城镇。
- 给定值均为整数。
子任务
- (3 点) D\leq 1.
- (7 点) N\leq 3\,000, (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
- (10 点) N\leq 3\,000.
- (11 点) (U_j,V_j)=(j,j+1) (1\leq j \leq N-1).
- (41 点) D=N-1, N \leq 150\,000.
- (28 点)没有额外的限制。
样本输入 1
5 2 2 2 0 1 3 1 2 2 3 2 4 4 5
示例输出 1
2 3 4 2 2
我们展示了 JOI 君在 s=1.
- 时间 0, JOI君在城里 1 并采取以下措施。
- 镇上的邮票站 1 还没有安装,所以JOI君没有盖章。
- JOI君目前的体力是 2。他搬到城里 2,这是与城镇相连的未访问城镇之一 1 在一条路边。
- JOI君的体力减少了 1,他到达城镇 2 时间 1.
- 镇上的邮票站 2 还没有安装,所以JOI君没有盖章。
- JOI君目前的体力是 1。他搬到城里 3,这是与城镇相连的未访问城镇之一 2 在一条路边。
- JOI君的体力减少了 1,他到达城镇 3 时间 2.
- 镇上的邮票站 3 已经安装好了,所以JOI君按下了印章。
- JOI君选择在这里结束集章活动。由于他至少盖过一次印章,所以盖章集会成功了。他在那里收到了一份礼物。
因此,当JOI君从城镇出发时 1 并完成镇上的集章活动 3,集章活动可以成功,所以有必要在镇上准备一份礼物 3。 当JOI君从城镇出发时 1,只能在城镇准备礼物 3 和 4,所以输出的第一行应该是 2.
还有,当JOI君从城镇出发时 2,只能在城镇准备礼物 3, 4,和 5,所以输出的第二行应该是 3.
该输入示例满足子任务的约束 3,6.
示例输入 2
5 1 0 1 2 1 2 1 2 2 3 3 4 4 5
示例输出 2
2 1 2 0 1
该输入示例满足子任务的约束 1,2,3,4,6.
示例输入 3
7 6 2 3 0 4 1 3 4 1 2 2 3 2 4 1 5 1 6 6 7
示例输出 3
2 2 7 5 1 2 5
该输入示例满足子任务的约束 3,5,6.