各辺について，今その辺を Union-Find で結んだ場合，何回 find が呼ばれるか，という値を保持することにします． 辺を結ぶたびにこの値を更新することを考えると，\(B_i\) 側の連結成分から出ているまだ処理していない辺の本数だけ，後に find を呼ぶ回数が増えます． 結局，問題を整理すると，次のようになります．

• 木の辺を好きな順序で縮約していく
• 頂点 \(u,v\) を縮約する際，\(u\) か \(v\) の好きな方の次数をスコアに加算する．
• 最終的なスコアの合計を最大化せよ．

これをもう少し整理して，以下のように定式化します．

• 各頂点に値を書くことにして，頂点 \(v\) の値を \(f_v\) で表す．最初，\(f_v=( v\) の次数 \(-2)\) で初期化する．
• 木の辺を好きな順序で縮約していく．
• 頂点 \(u,v\) を縮約する際，\(\max(f_u,f_v)\) をスコアに加算する．
• 縮約後の頂点には，\(f_u+f_v\) を書き込む．
• 最終的なスコアの合計を最大化せよ．

ここで，頂点に色という性質を追加します． 最初，すべての頂点は白であるとし，縮約によってできる頂点はすべて黒であるとします． ここで，最適解の構造について以下の主張が成り立ちます．

• ある最適解が存在して，その中では黒い頂点同士を縮約しない．

\(f_v\) の初期値に \(eps \times 2^v\) を足した場合の問題を考えてみます．これは，\(\max\) を取る際のタイブレークとして機能します． ここで，黒い頂点同士を結ぶような最適解が存在したとして，矛盾を導きます．

まず，最適解においては，葉の頂点はすべて最後に縮約して損しないことがわかります． よって，葉以外の頂点，つまり \(f_v > 0\) の頂点だけで話を進めます．

黒い頂点同士を結ぶ操作を適当に一つとり，そこで結ばれる頂点が \(u,v\) であるとします． \(u\) の元となった \(2\) つの頂点を \(a,b\)，\(v\) の元となった \(2\) つの頂点を \(c,d\) と置くことにします． 操作の順序を適切に入れ替えることで，スコアを変えないまま，\((a-b),(c-d),(u-v)\) の縮約がこの順に連続して行われるようにします． この \(3\) 回の操作のスコアは，\(\max(f_a,f_b)+\max(f_c,f_d)+\max(f_a+f_b,f_c+f_d)\) です． ここで，一般性を失わず，\(f_a+f_b>f_c+f_d\) だとします． また，\((u-v)\) で縮約される辺はもともと \(c\) に接続する辺だったとします． \(3\) 回の操作の順番を入れ替え，\((a-b),(u-v),(c-d)\) としてみると，そのスコアは \(\max(f_a,f_b)+\max(f_a+f_b,f_c)+\max(f_a+f_b+f_c,f_d)\) になります．これはもともとのスコアより真に大きいため，最初にとった解の最適性に矛盾しています．

よって，最適解の構造は，ある一つの頂点を基準として，そこに向かって頂点を一個ずつ縮約していく，という形だとわかります． また，\((u,v)\) を縮約する場合のスコアは \(\max(f_u,f_v)\) ですが，\(u\) を基準点側の頂点だとすると，このスコアは \(f_u\) だと思って問題ありません． もし \(f_u<f_v\) となる操作がある場合は，\(v\) を基準にしたほうがスコアが大きくなるためです．

基準点を \(N\) 通りすべて試すと，以下のような問題が解ければ良いことになります．

• 各頂点に値の書かれた根付き木が与えられる．
• 頂点を一列に並べる．ただし，列の中ではどの頂点についても，その先祖の頂点よりも前に現れてはいけない，
• \(\sum_i i \times (i\) 番目の頂点に書かれた値\()\) を最小化せよ．

ここまで定式化できればあとは有名問題です． すでに複数回出題されたことがあるので，解説はそちらの問題に譲ります．

計算量は全体で \(O(N^2 \log N)\) です．

解答例(C++)