ARC(AtCoder Regular Contest) 030 B - ツリーグラフ

B: ツリーグラフ - AtCoder Regular Contest 030 | AtCoder

[問題]

n頂点のツリーグラフがある。いくつかの頂点に宝石がある。頂点xから開始して、全部の宝石を取ってxに戻るには、最短で何個の辺を通ればいいか。

[回答]

頂点xから出発してDFS(深さ優先探索)で各頂点をたどる。

宝石が見つかった場合、その頂点およびその頂点からの戻りの頂点は必ず通る必要があるので、戻りの経路では+1をする。

また、宝石が見つかった場合、既に必ず通ることになっている頂点からの距離を追加する。

[コード](Ruby)

https://paiza.io/projects/YBHSiCwcpiyQyX020mRuvg

 [感想]

最初、戻りのことを忘れていた。

もう少し簡単な方法ないかな。。