10154번 - Zadanie 다국어

Bajtazar przygotowuje właśnie zadanie na konkurs programistyczny. Napisał już szkic treści:

W Bajtocji jest n miast połączonych n - 1 dwukierunkowymi drogami w taki sposób, że korzystając z sieci drogowej da się przejechać pomiędzy dowolnymi dwoma miastami. Przebycie drogi łączącej dwa bezpośrednio połączone miasta zajmuje jedną godzinę. Miasta są ponumerowane od 1 do n. W mieście i mieszka a_i mieszkańców.

W przyszłym roku w Bajtocji mają się odbyć wybory. Aby mieć pełną kontrolę nad przebiegiem głosowania, król Bajtocji postanowił, że głosowanie zostanie zorganizowane w tylko jednym mieście. Wszyscy mieszkańcy Bajtocji udadzą się najkrótszą drogą do miasta z urną wyborczą i tam oddadzą głos. Teraz pozostało wybrać miasto, w którym odbędzie się głosowanie. Wybór ten zależy od wielu czynników. W szczególności, dla każdego miasta i chcielibyśmy obliczyć łączny czas potrzebny wszystkim mieszkańcom Bajtocji na dotarcie do miasta i (oznaczmy tę wartość przez b_i) [...]

Bajtazar miał już przygotowane wyjątkowo trudne testy do zadania, jednak przypadkiem stracił połowę danych. Teraz z każdego testu pozostały mu tylko opisy połączeń drogowych i pliki wyjściowe zawierające wartości b_i. Na tej podstawie chciałby odtworzyć liczbę mieszkańców każdego miasta Bajtocji.

W pierwszym wierszu wejścia znajduje się liczba całkowita n (2 ≤ n ≤ 300 000) oznaczająca liczbę miast w Bajtocji. Każdy z kolejnych n - 1 wierszy zawiera opis jednego połączenia drogowego w postaci pary liczb całkowitych x_i, y_i (1 ≤ x_i, y_i ≤ n). Oznaczają one, że miasta x_i oraz y_i są połączone drogą.

Kolejny wiersz zawiera ciąg n liczb całkowitych b_i (0 ≤ b_i ≤ 10⁹).

Wypisz jeden wiersz z ciągiem n liczb całkowitych a_i. Liczba a_i powinna oznaczać liczbę mieszkańców miasta Bajtocji numer i. Dla podanego ciągu a_i, po rozwiązaniu zadania Bajtazara powinno się otrzymać ciąg b_i podany na wejściu.

Dane wejściowe są tak dobrane, że odpowiedź zawsze istnieje. Jeśli istnieje wiele poprawnych odpowiedzi, Twój program może wypisać dowolną z nich.