アイヅ国には$N$個の島と$N-1$個の橋があり、各島はそれぞれ$1$から$N$までの番号が割り振られている。 $i$番目の橋は島$u_i$と島$v_i$を双方向に結んでおり、島民は橋を用いて島と島とを行き来することができる。また、橋以外に島と島を行き来する方法はない。 どの島からどの島へもいくつかの橋を渡ることで到達することができる。
現在、島$i$には$X_i$人の島民がいる。 各島の環境への負荷を分散させるためにアイヅ国は何人かの国民に別の島へ引越してもらうことにした。 島$a$に住んでいる人を島$b$に引越しさせるためには島$a$と島$b$の距離と同じ分のコストがかかる。ただし、島$a$と島$b$の距離は島$a$から島$b$へ行くために渡る必要のある橋の数の最小値で定義される。
どの$2$つの島を選んでもそれらの島民の人数の差の絶対値が$1$以下になるように国民に引越してもらいたい。 このとき、必要なコストの総和の最小値を求めよ。
入力は以下の形式ですべて整数で与えられる。
$N$
$X_1$ $X_2$ ... $X_N$
$u_1$ $v_1$
$u_2$ $v_2$
...
$u_{N-1}$ $v_{N-1}$
$1$行目に島の数$N$が与えられる。
$2$行目には各島の島民の人数を表す$N$個の整数が空白区切りで与えられる。$i$番目の整数$X_i$は島$i$の島民の人数を表す。
$3$行目から続く$N-1$行には各橋がつなぐ島の番号が空白区切りで与えられる。$2+i$行目の入力では、$i$番目の橋が島$u_i$と島$v_i$を双方向に結んでいることを表す。
入力は以下の条件を満たす。
コストの総和の最小値を1行に出力せよ。
5 4 0 4 0 0 1 2 1 3 1 4 2 5
7
島$1$の人が$1$人、島$2$へ、
島$1$の人が$1$人、島$5$へ、
島$3$の人が$2$人、島$4$へ引っ越すことでどの$2$つの島を選んでもそれらの島民の人数の差の絶対値が$1$以下になる。
またこのときのコストの総和は$1+2+2\times2 = 7$であり、これが最小である。
7 0 7 2 5 0 3 0 1 2 1 3 1 4 2 5 3 6 3 7
10