Mines in a Tree

This problem is adapted from PA 2022 Runda 4 "Miny".

You are given a tree (an undirected acyclic connected graph) with n vertices. Each edge in the tree has a given positive length. Moreover, every vertex has a mine with a fixed explosion radius. When a mine explodes, it triggers all other mines located at a distance at most equal to its explosion radius. The distance between two vertices is defined as the sum of the lengths along the unique simple path connecting them.

For every mine, if you manually detonate it (considering each detonation independent), determine how many mines will eventually explode (including the initial one) due to the chain reaction.

More formally, if you manually detonate the mine at vertex i, it will cause the explosion of any mine at vertex j if there exists a sequence of vertices i = v₀, v₁, ..., v_k = j such that for each 0 ≤ t < k the following holds:

where \(d(u,v)\) is the distance between vertices \(u\) and \(v\) and \(r_u\) is the explosion radius at vertex \(u\). Compute the number of mines that will explode when the mine at each vertex is manually detonated.

inputFormat

The first line contains an integer n (the number of vertices).

Each of the next n-1 lines contains three integers: u v w, representing an edge between vertices u and v with length w. It is guaranteed that the given graph is a tree.

The last line contains n integers, where the i-th integer is the explosion radius \(r_i\) of the mine located at vertex i.

outputFormat

Output a single line with n integers. The i-th integer should be the total number of mines that will eventually explode if the mine at vertex i is manually detonated.

sample

3
1 2 1
2 3 1
1 1 1

3 3 3