삼국지

당신은 세계적으로 인기 있는 전쟁 시뮬레이션 게임 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|$의 최솟값을 출력한다.