아쉬움이 남지만

욱제는 자신이 낸 문제 계곡이 넘쳐흘러에 아쉬움이 남아, 백숙 장수가 된 욱제의 미래 삶을 상상하고 있다.

논산 훈련소 깊은 산속 논산골에는 4차산업혁명으로 선물 포장 공장이 망해서, 계곡에서 백숙을 팔며 살다가 훈련병으로 끌려간 욱제가 있다.

논산골에는 $N$개의 계단식 계곡이 있고, 이 계곡들은 $N - 1$개의 물길로 트리 형태로 연결되어 있다. 임의의 두 계곡 사이에는 경로가 하나뿐이다. $i$번째 계곡은 해발 $H_i$미터에 있다. 1번 계곡은 수원이며, 모든 물길은 수원에서 멀어지는 방향으로 흐른다.

사격 훈련 도중 욱제는 탄피 $N$개를 잃어버렸다. 탄피는 모든 계곡에 하나씩 떨어졌다. 욱제는 점프로 탄피를 찾아 회수하려고 한다.

해발 $H_a$미터인 계곡에서 해발 $H_b$미터인 계곡으로 점프하면($H_a \ge H_b$), 욱제는 $H_b$에서 $(H_a - H_b) / 2$미터만큼 튀어 오른다. 그러면 욱제는 해발 $H_b + (H_a - H_b) / 2$미터까지 올라가서, $H_c \le H_b + (H_a - H_b) / 2$를 만족하는 계곡으로 이동할 수 있다. 이어서 욱제는 $(H_b + (H_a - H_b) / 2 - H_c) / 2$미터만큼 다시 튀어 오른다. 욱제의 점프는 물길과 같은 방향으로만 이동할 수 있다. 점프 때문에 계곡의 높이가 변하거나 물길의 방향이 바뀌지는 않는다.

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

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

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

둘째 줄에 계곡의 해발 고도 $H_1, H_2, \ldots, H_N$이 공백으로 구분되어 주어진다.

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

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

$1 \le N \le 316,402$

$1 \le H_i \le 10^8$ ($1 \le i \le N$)

주어지는 물길 $N - 1$개는 계곡들을 트리 형태로 연결한다.