$K$국지

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

당신은 여러 국가를 건국하여 전쟁 시뮬레이션을 진행하려고 한다. 각 국가는 적어도 하나의 도시를 포함해야 하며, 각 도시는 정확히 하나의 국가에 속해야 한다. 또한 같은 국가에 속한 임의의 두 도시는 다른 국가의 도시를 거치지 않고 도로를 따라 이동할 수 있어야 한다.

국가가 지나치게 강하면 전쟁에서 쉽게 이기게 되어 게임의 재미가 떨어진다. 그래서 전투력을 균형 있게 나누는 것이 중요하다. 국가의 전투력은 그 국가에 포함된 모든 도시의 전투력의 합이다. 당신은 전투력 상한 $U$를 정했다. 각 국가의 전투력은 $U$를 넘지 않아야 하며, $k$ ($1 \leq k \leq N$)개의 국가가 전투력 $w_1, w_2, \dots, w_k$를 가질 때 $\sum_{i=1}^{k} (U-w_i)^2$이 최소가 되도록 나누는 것이 균형 잡힌 분배 방법이다. 이 기준에 따라 국가의 전투력을 균형 있게 분배하시오.

첫 번째 줄에 도시의 수 $N$이 주어진다. ($1 \leq N \leq 10\,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $i$번 도시의 전투력 $c_i$가 한 줄에 하나씩 주어진다. ($1 \leq c_i \leq 100$)

이어서 $N-1$개의 줄에 도로 정보가 주어진다. 각 줄에는 도로가 잇는 두 도시의 번호가 공백으로 구분되어 주어진다.

마지막 줄에 국가의 전투력 상한 $U$가 주어진다. ($\max_{1 \leq i \leq N} c_i \leq U \leq 100$)

$\sum_{i=1}^{k} (U-w_i)^2$의 최솟값을 출력한다.