31232번 - 삼국지

문제

당신은 세계적으로 인기 있는 전쟁 시뮬레이션 게임 shake!를 플레이하고 있다. 게임 내에는 1ドル$번부터 $N$번까지 번호가 매겨져 있는 $N$개의 도시가 있으며 각 도시는 전투력을 가진다. 또한, 서로 다른 두 도시를 양방향으로 잇는 $N-1$개의 도로가 있으며 도로를 따라 임의의 도시 간 이동이 가능하다.

당신은 세 국가를 건국하여 전쟁 시뮬레이션을 진행하려고 한다. 각 국가는 적어도 하나의 도시를 포함해야 하며 각 도시는 정확히 하나의 국가에 포함되어야 한다. 또한, 다른 국가의 도시를 거치지 않으면서 도로를 따라 국가 내 임의의 도시 간 이동이 가능해야 한다.

어떤 국가가 지나치게 강력하여 쉽게 삼국을 통일하면 게임의 재미가 떨어지므로 전투력을 균형 있게 분배하는 것이 중요하다. 국가의 전투력은 국가에 포함된 모든 도시의 전투력의 합으로 정의된다. 고민 끝에 당신은 세 국가의 전투력을 각각 $a,b,c$라 할 때, $\left|a-b \right| + \left|b-c \right| + \left|c-a \right|$를 최소로 하는 것이 전투력을 균형 있게 분배하는 방법이라고 결론 지었다. 삼국의 전투력을 균형 있게 분배하시오.

입력

첫째 줄에 도시의 수 $N$이 주어진다. $(3\leq N \leq 200,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐, $i$번째 줄에는 $i$번 도시의 전투력이 양의 정수로 주어진다. 모든 도시의 전투력의 합은 10ドル^9$을 넘지 않는다.

그다음 줄부터 $N-1$개의 줄에 걸쳐 도로의 정보가 주어진다. 각 줄에 각 도로가 잇는 두 도시의 번호가 공백으로 구분되어 주어진다.

출력

첫째 줄에 $\left|a-b \right| + \left|b-c \right| + \left|c-a \right|$의 최솟값을 출력한다.

제한

힌트