题目描述

题目译自 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

数据规模与约定

对于所有数据，保证：

$1 \le n \le 100,000$

$0 \le r_i \le 10^{18}$

$1 \le c_i \le 10^{12}$

样例解释：

输入的树结构如图所示（图略）。

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

节点 $2$ 的地雷爆炸半径只有 $1$，所以只能引爆自己。 节点 $3$ 的地雷爆炸半径为 $0$，所以只能引爆自己。 节点 $5$ 的地雷爆炸半径为 $6$，可以引爆节点 $2$ 和 $5$，所以总共 $2$ 个。