26723번 - Miny 다국어

„A może odkopmy jakieś stare zadanie z ciągiem i każmy je zrobić na drzewie?”

---

Autor zadania

Dane jest drzewo (nieskierowany graf acykliczny) w którym każda krawędź ma pewną długość. W każdym wierzchołku tego drzewa znajduje się mina o pewnym promieniu rażenia. Jeśli jakaś mina wybuchnie, to wybuchną też miny we wszystkich wierzchołkach odległych o nie więcej niż promień rażenia tejże miny. Odległość między dwoma wierzchołkami definiujemy jako sumę długości krawędzi na ścieżce prostej między nimi. Określ, dla każdej z min, ile min wybuchnie, gdy tę jedną zdetonujemy „ręcznie”. Zwróć uwagę, że dla każdej miny, jej ręczną detonację rozważamy niezależnie od ręcznych detonacji innych min.

W pierwszym wierszu wierszu standardowego wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 100 000), oznaczająca liczbę wierzchołków drzewa (a zarazem liczbę min). Wierzchołki drzewa numerujemy liczbami całkowitymi od 1 do n.

W drugim wierszu znajduje się n liczb całkowitych r₁, r₂, . . . , r_n (0 ≤ r_i ≤ 10¹⁸), gdzie r_i oznacza promień rażenia miny znajdującej się w i-tym wierzchołku.

W kolejnych n−1 wierszach znajdują się po trzy liczby całkowite a_i, b_i oraz c_i (1 ≤ a_i, b_i ≤ n; 1 ≤ c_i ≤ 10¹²), które oznaczają, że istnieje krawędź długości c_i łącząca wierzchołki a_i oraz b_i.

Gwarantujemy, że wejście zawiera poprawny opis drzewa.

W jedynym wierszu wyjścia powinno znaleźć się n liczb, gdzie i-ta z nich powinna być równa liczbie min, które wybuchną, jeśli ręcznie zdetonujemy minę znajdującą się w i-tym wierzchołku drzewa.

Wyjaśnienie przykładu: Drzewo w teście przykładowym wygląda następująco:

Gdy ręcznie zdetonujemy minę znajdującą się w czwartym wierzchołku, jej wybuch spowoduje detonację min znajdujących się w pierwszym oraz drugim wierzchołku, zaś w efekcie mina znajdująca się w pierwszym wierzchołku spowoduje wybuch miny znajdującej się w piątym wierzchołku. W sumie wybuchną zatem cztery miny.