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