Problem Description

This problem is translated from PA 2022 Round 4 Miny.

You are given a tree (an undirected acyclic graph). Each edge of the tree has a fixed length. There is a mine at each node, and each mine has a fixed blast radius. If a mine explodes, then all mines whose distance to this mine is at most its blast radius will also explode.

The distance between two nodes is defined as the sum of edge lengths on the simple path between them. For each mine, if we manually detonate it, determine how many mines will explode. Note that for each mine, we consider manually detonating it to be independent of manually detonating any other mine.

Input Format

The first line contains an integer $n$, the number of nodes in the tree (also the number of mines). The nodes are numbered from $1$ to $n$.

The second line contains $n$ integers $r_1, r_2, \ldots, r_n$, where the $i$-th integer is the blast radius of the mine at node $i$.

The next $n - 1$ lines each contain three integers $a_i, b_i, c_i$, meaning there is an edge of length $c_i$ connecting nodes $a_i$ and $b_i$.

It is guaranteed that the input describes a tree.

Output Format

For $100\%$ of the testdata, the following is required:

Output one line with $n$ integers. The $i$-th integer should be the number of mines that will explode if we manually detonate the mine at node $i$.

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

4 1 1 4 2

Hint

$1 \le n \le 10^5$, $0 \le r_i \le 10^{18}$, $1 \le a_i, b_i \le n$, $1 \le c_i \le 10^{12}$.

Translated by ChatGPT 5