AOJ 0235 （Sergeant Rian : サージェント・ライアン）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0235

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0235

【解説】

サンプルや画像から自明ではあるが、1の島を根とした木の探索とみなすことができる。

結論から先に言うと、葉に繋がる橋以外の橋を渡るのに必要な時間の2倍から、根から最も遠い、葉のノードの親となるノード（以下"葉親"とする）に到達するまでに必要な時間を引いた値が解となる。

まず、橋を爆破するには、その手前の島まで到達すればよい。そのため、葉となる島を訪れることはない。また逆に全ての葉に繋がる橋を爆破するため、全ての葉親を訪れる必要がある。

よって、葉親までのノードを深さ優先で訪問していき、最後の葉親に到達するまでの経路が全ての橋を爆破できる経路となる。（巡回しながら、訪問したノードに葉があれば葉に繋がる橋を爆破し、島に入ってきた橋以外の橋が無くなれば、その橋を渡って島から出た後、その橋を爆破することで、橋の残る島が分断されることなく爆破していける）

上記の経路は、最後に到達する葉親をどのノードにするかによって、複数の経路をとることができる。例えば、サンプルであれば最後の葉親を3にするか5にするかの経路の２通りが存在する。

これらの経路のうち、どれが最短となるかであるが、"葉親までのノードを深さ優先で訪問していき、最後の葉親に到達するまでの経路"とは、すなわち、"葉親までの全てのノードを深さ優先探索で検索して根に戻る経路"（①）から、"根から最後の葉親"（②）までの経路を引いた経路となる。

①の時間は、全ての橋を往復する時間となるため、最後の葉親に関わらず等しくなる。よって、最短時間の経路は②が最大となる経路であり、最後に訪れる葉親を根から最も到達時間の長い葉親とすればよいこととなる。

そのため、冒頭のとおり、葉に繋がる橋以外の橋を渡るのに必要な時間の2倍から、根から最も遠い葉親に到達するまでに必要な時間を引いた値を求めればよい。

①と②の時間については、木の深さ優先探索にて求めていった。（関数GetAllTime,GetLongestTime参照）葉を訪れないようにするため、各ノードを抽出する際、子があるノードのみを抽出するようした。

【コード】