[AdditionalFile3913.zip](file://AdditionalFile3913.zip?type=additional_file)

#3913. 「PA 2022」Miny

标签: 传统 | 时间限制: 9000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2022 Runda 4 Miny

挖一些远古题然后把它放树上怎么样？

——出题人

给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗地雷不超过其爆炸半径的地雷都会爆炸。我们定义两个点之间的距离是这两个点之间简单路径上边的长度和。对于每颗地雷，如果手动引爆它，确定有多少地雷会爆炸。注意对于每颗地雷，我们认为手动引爆它与手动引爆其他地雷互相独立。

输入格式

第一行包含一个整数 $n\ (1\le n\le 100\ 000)$，表示树的节点数（也是地雷个数）。树节点编号是从 $1$ 到 $n$ 的整数。

第二行 $n$ 个整数 $r_1,r_2,\ldots,r_n\ (0\le r_i\le 10^{18})$，第 $i$ 个整数为位于节点 $i$ 的地雷的爆炸半径。

接下来 $n-1$ 行，每行三个整数 $a_i,b_i,c_i\ (1\le a_i,b_i\le n,1\le c_i\le 10^{12})$，表示一条长 $c_i$ 的边连接节点 $a_i$ 和 $b_i$。

保证输入可以正确表示一棵树。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示如果我们手动引爆在节点 $i$ 上的地雷，有多少地雷会爆炸。

样例

输入

5
8 1 0 4 6
2 4 2
3 1 9
2 5 5
2 1 2

输出

4 1 1 4 2

输入的树如图所示：

当我们手动引爆节点 $4$ 上的地雷时，它的爆炸会使得节点 $1$ 和 $2$ 的地雷爆炸，而节点 $1$ 的地雷爆炸同时会引起在节点 $5$ 上的地雷爆炸。所以一共有 $4$ 颗地雷爆炸。