Mines

"Maybe we could dig up some old problem with a sequence and have them solve it on a tree?"

---

Problem author

You are given a tree (an undirected acyclic graph) where every edge has a length. Each vertex of the tree holds a mine with a blast radius. When a mine explodes, every mine at a vertex within distance at most its blast radius also explodes, and the chain continues. The distance between two vertices is the sum of the edge lengths on the simple path between them. For each mine, determine how many mines explode when you detonate that one mine by hand. Each manual detonation is considered independently of the manual detonations of the other mines.

The first line contains an integer $n$ ($1 \le n \le 100000$), the number of vertices in the tree, which is also the number of mines. The vertices are numbered from 1 to $n$.

The second line contains $n$ integers $r_1, r_2, \ldots, r_n$ ($0 \le r_i \le 10^{18}$), where $r_i$ is the blast radius of the mine at vertex $i$.

The next $n-1$ lines each contain three integers $a_i$, $b_i$, $c_i$ ($1 \le a_i, b_i \le n$; $1 \le c_i \le 10^{12}$), meaning there is an edge of length $c_i$ connecting vertices $a_i$ and $b_i$. The input is guaranteed to describe a valid tree.

Print one line with $n$ integers. The $i$-th integer is the number of mines that explode when you detonate the mine at vertex $i$ by hand.

Explanation of the example: the example tree is shown below.

When the mine at the fourth vertex is detonated by hand, its blast sets off the mines at the first and second vertices. The mine at the first vertex then sets off the mine at the fifth vertex. In total, four mines explode.