ABC014 D.閉路

その他 過去問

問題

無向木が与えられる。
クエリとして、頂点a,bが与えられるとき、aとbに辺を追加したら閉路ができる。このとき、閉路を形成する辺の数を返す。

V <= 10^5
Q <= 10^5

考え方

Qが10^5まであるので、O(n)な解法だと間に合わない。
頂点aから頂点bまでの距離がわかっていれば、それに+1したものが閉路の辺数になることがわかる。
これを高速に求められればよい。


根付き木の場合、2頂点の共通の祖先ノードで一番近いノードをLCA(最小共通祖先)という。
すると、(根から頂点aまでの深さ - 根からLCAまでの深さ) + (根から頂点bまでの深さ - 根からLCAまでの深さ)が頂点a,b間の距離になる。
ダブリングによる実装(参照：蟻本)の場合、構築がO(n log n)、探索がO(log n)なので、間に合う。
(根から頂点vまでの深さは、構築がO(n)、探索がO(1))


ちなみに、本番ではサボって、TarjanによるUnionFindとdfsによる解法(参照：spaghetti source)を使ったところ、TLEしてしまった。。。