주민 수 복원

바이타자르는 프로그래밍 대회에 낼 문제를 준비하고 있다. 문제 초안은 이미 써 두었다.

바이토차에는 도시가 $n$개 있고, 양방향 도로 $n - 1$개가 도시를 잇는다. 도로망을 이용하면 어느 두 도시 사이든 오갈 수 있다. 직접 연결된 두 도시를 잇는 도로를 지나는 데는 한 시간이 걸린다. 도시에는 $1$번부터 $n$번까지 번호가 붙어 있고, $i$번 도시에는 주민 $a_i$명이 산다.

내년에 바이토차에서 선거가 열린다. 투표 과정을 완전히 통제하려고 바이토차의 왕은 투표를 도시 한 곳에서만 진행하기로 했다. 바이토차의 모든 주민은 투표함이 있는 도시까지 최단 경로로 이동해 그곳에서 투표한다. 이제 투표를 진행할 도시를 고르는 일만 남았는데, 이 선택은 여러 요인에 달려 있다. 특히 각 도시 $i$마다 바이토차의 모든 주민이 $i$번 도시까지 오는 데 걸리는 시간의 합을 계산하고 싶다. 이 값을 $b_i$라 하자. [...]

바이타자르는 이 문제에 쓸 아주 까다로운 테스트를 이미 만들어 두었지만, 실수로 자료의 절반을 잃어버렸다. 지금 각 테스트에 남은 것은 도로 연결을 적은 부분과 $b_i$ 값이 담긴 출력 파일뿐이다. 바이타자르는 이것만 가지고 바이토차 각 도시의 주민 수를 복원하려 한다.

첫 줄에 바이토차의 도시 수를 뜻하는 정수 $n$ ($2 \le n \le 300000$)이 주어진다. 이어지는 $n - 1$개 줄에는 도로 하나를 나타내는 두 정수 $x_i$, $y_i$ ($1 \le x_i, y_i \le n$)가 주어진다. $x_i$번 도시와 $y_i$번 도시가 도로로 이어져 있다는 뜻이다. 도로망은 모든 도시를 잇는다.

그다음 줄에는 정수 $n$개로 이루어진 수열 $b_i$ ($0 \le b_i \le 10^9$)가 주어진다.

정수 $n$개로 이루어진 수열 $a_i$를 공백으로 구분해 한 줄에 출력한다. $a_i$는 바이토차 $i$번 도시의 주민 수다. 출력한 수열 $a_i$로 바이타자르의 문제를 풀면 입력으로 주어진 수열 $b_i$가 나와야 한다.

입력은 답이 항상 존재하도록 주어진다. 도로망과 수열 $b_i$가 정해지면 조건을 만족하는 수열 $a_i$는 하나뿐이므로, 그 수열을 출력한다.