지뢰

"옛날 수열 문제를 꺼내서 이번에는 트리 위에서 풀게 하면 어떨까?"

---

문제 저자

간선마다 길이가 정해진 트리(사이클이 없는 무방향 그래프)가 주어진다. 각 정점에는 폭발 반경이 정해진 지뢰가 하나씩 놓여 있다. 어떤 지뢰가 폭발하면, 그 지뢰의 폭발 반경 이하의 거리에 있는 정점의 지뢰도 모두 폭발한다. 이 연쇄는 계속된다. 두 정점 사이의 거리는 두 정점을 잇는 단순 경로 위 간선 길이의 합이다. 각 지뢰에 대해, 그 지뢰 하나를 손으로 직접 터뜨렸을 때 몇 개의 지뢰가 폭발하는지 구하라. 손으로 터뜨리는 경우는 지뢰마다 독립적으로 생각한다.

첫 줄에 정수 $n$ ($1 \le n \le 100000$)이 주어진다. 이는 트리의 정점 수이자 지뢰의 개수이다. 정점은 1부터 $n$까지 번호가 매겨져 있다.

둘째 줄에 정수 $r_1, r_2, \ldots, r_n$ ($0 \le r_i \le 10^{18}$)이 주어진다. $r_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$번 정점의 지뢰를 손으로 터뜨렸을 때 폭발하는 지뢰의 개수이다.

예시 설명: 예시 트리는 다음과 같다.

네 번째 정점의 지뢰를 손으로 터뜨리면 그 폭발로 첫 번째와 두 번째 정점의 지뢰가 터진다. 그러면 첫 번째 정점의 지뢰가 다섯 번째 정점의 지뢰를 터뜨린다. 따라서 모두 네 개의 지뢰가 폭발한다.