UVa10938 Flea circus

問題
http://uva.onlinejudge.org/external/109/10938.html

概要
ノードとノードの接続関係を表した木の情報が与えられる。あるノード２点にノミがいて、それらは相手のノミに向かって最短で移動しようとする。最後に一つのノードに終着する場合と、お互い隣のノードを行き来して飛び交う場合がある。

解法
経路を保持しつつ bfs して単一始点最短路を求める。経路を vector で持ったとき、そのサイズの偶奇で出力に場合分けが生じる。偶数の場合は２匹は飛び交うが、このときノード番号出力の順を注意する。また与えられるノードが 1-indexed であるので、入力だけでなく出力のときもそれを気にする。