問題

$N$ 個の整数が書かれたボールが箱に入っており, $i$ 番目のボールには整数 $A_i$ が書かれている.

次の操作を $(N-1)$ 回行う.

得られる得点の最大値を求めよ.

$1 \leq i_p \lt j_p \leq N$ に対して, $(i_1, j_1), \dots, (i_{N-1}, j_{N-1})$ について, 以下は同値になる.

(a) 順番及び食べるボールを適切に選ぶことによって, $1 \leq p \leq N-1$ の任意の整数 $p$ において, $i_p$ 番目のボールと $j_p$ 番目のボールをペアで選び出すことができる.
(b) $V:=\{1,2, \dots, N\}, E:=\{i_1 j_1, \dots, i_{N-1} j_{N-1} \}$ として, $T:=(V,E)$ は木になる.

証明

(a) が成り立つとき, $T$ において, $i\_p$ 番目のボールと $j\_p$ 番目のボールをペアで選び出し, $i_p$ 番目のボールを食べるという操作を行った時, 頂点 $i_p$ を頂点 $j_p$ に縮約させるという行動を行う. すると, 残っている頂点と残っているボールの番号が等しくなる. よって, $(N-1)$ 回の操作後に $T$ に残る頂点は1頂点である. よって, $T$ は $N$ 頂点 $(N-1)$ 辺の連結グラフであるから, 木である.
(b) が成り立つとき, 次のようなアルゴリズムを繰り返すことによって, の任意の整数において, 番目のボールと番目のボールをペアで選び出すことができる.
- 以下の行動を $1$ 頂点になるまで繰り返す.
- $T$ は木であるから, 葉 $u$ が存在する. $u$ の唯一の近傍を $v$ とする.
- $u$ 番目のボールと $v$ 番目のボールを選び, $u$ 番目のボールを食べる.
- この行動は $T$ から頂点 $u$ を削除することを意味する.
これにより, (a) が成り立つような手順を構成できた.