$K$ Nations

You are playing shake!, a war simulation game popular around the world. The game has $N$ cities numbered from 1 to $N$, and each city has a combat power. There are also $N-1$ roads that connect two different cities in both directions, and you can travel between any two cities along the roads.

You plan to found several nations and run a war simulation. Each nation must contain at least one city, and each city must belong to exactly one nation. Any two cities in the same nation must be connected by roads without passing through a city of another nation.

Splitting combat power evenly matters. A nation that is too powerful wins wars too easily, and the game loses its appeal. The combat power of a nation is the sum of the combat powers of all cities in it. You set a combat power cap $U$. No nation may exceed $U$, and if $k$ ($1 \leq k \leq N$) nations have combat powers $w_1, w_2, \dots, w_k$, the balanced split is the one that minimizes $\sum_{i=1}^{k} (U-w_i)^2$. Split the combat power of the nations this way.

The first line contains the number of cities $N$. ($1 \leq N \leq 10\,000$)

The next $N$ lines each contain the combat power $c_i$ of city $i$. ($1 \leq c_i \leq 100$)

The next $N-1$ lines describe the roads. Each line contains the two city numbers that the road connects, separated by a space.

The last line contains the combat power cap $U$. ($\max_{1 \leq i \leq N} c_i \leq U \leq 100$)

Print the minimum value of $\sum_{i=1}^{k} (U-w_i)^2$.