18862번 - 아쉬움이 남지만

욱제는 자신이 냈던 문제 계곡이 넘쳐흘러에 아쉬움이 남아 백숙 장수 욱제가 미래에 어떤 삶을 살고 있을지 상상하는 중이다.

논산 훈련소 깊은 산속 논산골 계곡에, 4차산업혁명으로 선물 포장 공장이 망해서 계곡에서 백숙을 팔며 연명하다 훈련병으로 끌려간 욱제가 살고 있다. 논산골에는 N개의 계단식 계곡이 있고, 이 계곡들은 N - 1개의 물길을 통해 트리 형태로 연결되어 있다. 즉, 임의의 두 계곡 사이에는 항상 유일한 경로가 존재한다. i번째 계곡은 해발 H_i미터에 위치해 있다. 1번째 계곡은 수원으로, 모든 물길은 수원에서 멀어지는 방향으로 흐른다.

안타깝게도 욱제는 사격 훈련 도중 탄피를 분실하고 말았다. 욱제가 잃어버린 탄피 N개는 모든 계곡에 하나씩 떨어졌다고 한다. 욱제는 탄피를 회수하기 위해 점프를 통해 탄피를 찾아 이동하려고 한다.

해발 H_a미터인 계곡에서 해발 H_b미터인 계곡으로 점프한 욱제는 H_b로부터 (H_a - H_b) / 2미터만큼 튀어 오른다. (H_a ≥ H_b) 그러면 욱제가 해발 H_b + (H_a - H_b) / 2미터까지 올라가서 H_c ≤ H_b + (H_a - H_b) / 2를 만족하는 계곡으로 이동할 수 있다. 그러면 욱제는 또 (H_b + (H_a - H_b) / 2 - H_c) / 2미터만큼 점프하게 된다. 욱제의 점프는 물길과 같은 방향으로만 이동할 수 있다. 욱제의 점프로 인해 계곡의 높이가 변하거나 물길의 방향이 바뀌는 일은 없다고 하자.

(a → b는 욱제가 a에서 b로 점프함을 나타내며, a와 b는 편의상 두 계곡의 높이라고 하자) 8 → 2인 경우 욱제는 (8 - 2) / 2 = 3미터만큼 점프하여 해발 5미터까지 올라간다. 그러면 최대 8 → 2 → 5까지 이동할 수 있다. 8 → 2 → 6, 8 → 2 → 7 등은 불가능하다. 8 → 2 → 2인 경우, 8 → 2를 통해 해발 5미터까지 점프한 욱제가 그 다음 해발 2미터의 계곡으로 떨어져서, (5 - 2) / 2 = 1.5미터만큼 점프하여 마지막에는 해발 3.5미터가 된다. 위 예제는 8에서 출발하면 모든 계곡에 도달할 수 있다.  

욱제는 자기가 있는 계곡이 어디인지조차 모른다. 욱제를 위해 각각의 계곡에 욱제가 있다고 가정할 때, 회수 가능한 탄피는 몇 개인지 구해주자! 단, 욱제는 스스로를 무한히 복제할 수 있기 때문에 각각의 복제된 욱제가 다른 길로 가서 탄피를 회수할 수도 있다.

첫째 줄에는 계곡의 개수 N이 주어진다.

둘째 줄에는 계곡의 해발 고도 H₁, H₂, ...,  H_N이 공백으로 구분되어 주어진다.

셋째 줄부터 N - 1개의 줄에는 각 물길이 연결하는 두 계곡의 번호가 공백으로 구분되어 주어진다.

하나의 줄에 N개의 수를 공백으로 구분하여 출력한다. i번째 수에는 욱제가 i번째 계곡에 있다고 가정했을 때 회수 가능한 탄피의 개수를 출력해야 한다.

• 1 ≤ N ≤ 316,402
• 1 ≤ H_i ≤ 10⁸ (1 ≤ i ≤ N)
• 주어지는 물길 N - 1개는 계곡들을 트리 형태로 연결한다.