ABC209 D Collision

この問題はABC126 D Even Relationのように木の二部グラフ性を用いて解くことができるが, ここでは別の解法を示す.

実は木上においては, LCA(最小共通祖先)を求めるアルゴリズムを用いることで, 全頂点対最短経路問題を前処理$ O(N \log N), クエリ当たり$ O(1)で求めることができる. なお, LCAとはある2頂点の共通祖先であって, 最も木の根から遠いものをいう. LCAはダブリングと呼ばれるアルゴリズムを用いることで求められる. 詳しくはダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズムを見ていただきたい.

よって, この問題を$ O(N \log N + Q)で解くことができた.

実装例: https://atcoder.jp/contests/abc209/submissions/24119329