問題
atcoder.jp
解法
街がN、経路がN-1であることから木構造であることがわかる。
木構造の頂点間の最短距離が奇数なら道で。
偶数なら街で出会う。
最短距離の偶奇を求めるために、各頂点の深さを計算。
深さから、頂点間の距離がわかる。
途中に共通の祖先（LCA）があったとしても距離の偶奇には関連しない。
c, d間の最短距離は
dep[c] + dep[d] - dep[lca] * 2
となる。
lcaは2倍されているので常に偶数。
ゆえに答えに関連しない。
実装
参考
youtu.be
