31839번 - 불꽃놀이의 아름다움

문제

봄 축제 때 정보과학관에서는 아무 행사도 진행되지 않는다는 것에 화가 난 찬솔이는 정보과학관 입구 앞에서 직접 불꽃놀이 행사를 진행하려고 한다.

정보과학관 입구 앞에 폭죽 또는 스위치를 설치할 수 있는 $N$개의 공간과, 서로 다른 두 공간을 연결하는 도화선 $N-1$개가 준비되어 있다. $N$개의 공간은 도화선을 통해 모두 서로 연결되어 있다. 찬솔이는 $N$개의 공간 중 한 곳에 스위치를 설치하고, 나머지 $N-1$개의 공간에는 폭죽을 설치한다. 만약 $i$번째 공간에 스위치가 설치되지 않았다면, $i$번째 공간에는 $W_i$개의 폭죽이 설치된다.

스위치를 설치한 공간의 번호를 $a$라고 하자. 공간 $x$와 $y$ 사이의 거리 $D(x,y)$는 $x$에서 $y$까지 이동하는 데 거쳐 가는 도화선의 최소 개수로 정의된다. 폭죽이 설치된 각 공간 $b$에서 터지는 폭죽의 아름다움은 $W_b\times D(a,b)$이다.

불꽃놀이의 아름다움은 스위치가 설치된 공간 $a$를 제외하고, 폭죽이 설치된 모든 공간 $b$에서 터지는 폭죽의 아름다움의 합으로 정의된다. 스위치를 설치할 공간을 잘 정해서 얻을 수 있는 불꽃놀이의 아름다움의 최댓값을 구해보자.

입력

첫째 줄에 공간의 수 $N$이 주어진다.

둘째 줄부터 $N-1$개의 줄에 걸쳐 도화선이 연결하는 두 공간의 번호 $a,b$가 공백으로 구분되어 주어진다.

$N+1$번째 줄에 $N$개의 정수 $W_1,W_2,\cdots ,W_N$이 공백으로 구분되어 주어진다.

출력

가능한 불꽃놀이의 아름다움 중 최댓값을 출력한다.

제한

• 2ドル\leq N\leq 200,円 000$
• 1ドル\leq a,b\leq N$
• 1ドル\leq W_i\leq 10^6$
• $N$개의 공간은 도화선을 통해 서로 연결되어 있다.
• 입력으로 주어지는 수는 모두 정수이다.

노트

정답이 32비트 정수 범위를 벗어날 수 있으므로 C/C++에서는 long long 타입, Java에서는 long 타입을 사용하는 것을 권장한다.

입출력 양이 많으므로 문제지 2-4페이지의 언어 가이드에 있는 빠른 입출력을 사용하는 것을 권장한다.