AGC018-Dを解いた.
問題
頂点重み付き木が与えられる.
の順列
を選び、そのスコアを
と定める(
:=頂点
と頂点
の距離). スコアの最大値を出力せよ.
解説
まずスコアにを加えたものを考える.
主客転倒を考えればこの最大値は各辺について次の値を計算して足し合わせた値である(この値をとでも置いておく).
- 辺の重み
その辺を切った時の小さいほうの連結成分のサイズ
の移動で重心をまたぐように
を決めていけば達成できる.
このことを踏まえて、と
をそれぞれ
として固定したときにスコアの最大値が何になるか考える.
(i) 重心が一つ
重心をと置くと、スコアは
となる.
この最大値は簡単に求められる.
(ii) 重心が二つ
重心間の辺の重みをと置くと、
が達成でき、これが最大値である.
(i)とほぼ同じこと.
考察
重心分解初めて使った. 上界達成可能なんじゃね? というのは大事だね.
