창고

바이토시아의 도로망은 어떤 도시 쌍들을 잇는 양방향 도로들로 이루어져 있습니다. 이 도로망은 어떤 도시에서든 다른 모든 도시로 정확히 한 가지 방법으로만, 그리고 도중에 어떤 도시도 두 번 이상 지나지 않고 갈 수 있도록 설계되어 있습니다. 즉, 도로망은 하나의 트리를 이룹니다.

각 도시에는 창고가 하나씩 있습니다. 바이타자르 왕은 어떤 물품 $T$톤을 주문했습니다. 이 물품은 모든 창고에 고르게 나뉘어 있어야 했지만, 공급자의 실수로 어떤 창고에는 너무 많이, 어떤 창고에는 너무 적게 들어가고 말았습니다. 배달된 물품을 창고들 사이에서 옮겨 모든 창고에 같은 양이 들어 있게 하려면 최소 얼마의 비용이 드는지 구하는 것을 도와주세요.

도로로 직접 연결된 두 도시 사이에서 물품 $1$톤을 옮기는 비용은 $1$입니다.

다음을 수행하는 프로그램을 작성하세요.

• 바이토시아 도로망과 창고들의 현재 물품 분포를 표준 입력에서 읽고,
• 모든 창고의 물품 양을 같게 만드는 최소 이동 비용을 구한 뒤,
• 그 결과를 표준 출력에 출력합니다.

첫째 줄에는 바이토시아의 도시 수를 나타내는 정수 $n$ ($1 \le n \le 500\,000$)이 주어집니다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있습니다.

둘째 줄에는 $n$개의 정수 $t_1, t_2, \dots, t_n$ ($0 \le t_i \le 100\,000\,000$)이 공백 하나로 구분되어 주어집니다. $t_i$는 $i$번 도시의 창고에 현재 들어 있는 물품의 양(톤)입니다. 전체 물품의 양 $T = t_1 + \dots + t_n$은 $n$으로 나누어떨어진다고 가정해도 좋습니다.

이어지는 $n - 1$개의 줄에는 도로 정보가 주어집니다. 그중 $j$번째 줄에는 두 정수 $a_j$와 $b_j$ ($1 \le a_j < b_j \le n$)가 공백 하나로 구분되어 주어지며, 이는 도시 $a_j$와 $b_j$를 잇는 도로를 뜻합니다.

첫째 줄에 정수 하나를 출력합니다. 이는 모든 창고에 최종적으로 $T/n$톤씩 들어 있게 만드는 최소 이동 비용입니다.

위 그림에서 사각형 안의 수는 해당 창고에 들어 있는 물품의 양이고, 나머지 수는 그 창고가 있는 도시의 번호입니다. 이 경우 목표는 모든 창고에 $12/6 = 2$톤씩 들어 있게 하는 것입니다. 최소 비용 $10$으로 이를 이루는 한 가지 방법은 다음과 같습니다.

• 도시 $1$에서 도시 $4$로 물품 $1$톤을 옮긴다 (비용 $2$),
• 도시 $1$에서 도시 $3$으로 물품 $2$톤을 옮긴다 (비용 $4$),
• 도시 $5$에서 도시 $6$으로 물품 $2$톤을 옮긴다 (비용 $4$).