1196. Bridge Removal

問題

木が与えられる。
木の辺を以下のルールで削除していく。
・最初にどこかのノードを決める
・ノードから辺を渡って別のノードへ移動する
・今いるノードにつながる辺を一つ削除し、今いるノードにとどまる
辺が無いノードには移動できない。

削除や移動にかかるコストは、辺の重みであるとき、すべての辺を削除する最小コストを返す。

考え方

葉ノードは、渡らずにその一つ手前のノードで削除すればよい。
葉ノード以外の部分について、考えると、木の直径(一番パスのコスト合計が大きい2ノード、最遠頂点対間距離)のパス(xノード間の辺)は「通って削除」で押さえて、直径パスじゃないところ(oノードに移動する辺)は、「行って戻って削除」するのが最小になる。
よって、求める最小コストは、葉ノードにつながる辺コスト＋2*直径＋3*(直径以外の辺コスト合計)になる。

  o
  |
x-x-x-x-x 直径
    |
    o
    |
    o

木の直径は、(たぶん)全点間最小距離を求めても大丈夫かもしれないが、double sweep法という、ある頂点から一番遠い点を求めて、さらにその点から一番遠い点を求めると、二回目に求めた2点が直径になっているというアルゴリズムだと、全部の辺を一回だけしか通らなくて済むのでO(E)で求められる。