公式解説にあるとおり、頂点\(a\)から\(b\)への経路は1通りになります。

そのため、構築される道路は森になります。

森だと扱いづらいので、連結成分ごとに適当に頂点をとって超頂点に連結して\(N+1\)頂点の木 \(G\) を構築しておきます。

また、ここで構築した木 \(G\) のオイラーツアーも求めておきます。

突然ですが、オイラーツアーの入るイベントで\(1\)、出るイベントで\(-1\)とする配列を考えます。すると根から頂点\(a\)に入るイベントまでの総和が\(a\)から根までの辺の数になります。これは、fenwick_treeやsegtreeを用いることで、\(O(log N)\)で求められます。

道を舗装するのを 「入る/出るイベントの値を\(0\)に書き換える」とすると、根から入るイベントまでの総和は「\(a\)から根までの舗装されていない辺の数」となります。LCAと組み合わせることで、\(a\)と\(b\)の間の舗装されていない辺の数を\(O(log N)\)で求められます。

更新クエリ

更新クエリを高速に構築できれば

2つの\(N+1\)頂点のUnion-Find \(U_1, U_2\)を用意します。

通常のUnionFindでは2つの木のマージをランクや要素数に基づいてマージすることで\(O(α(N))\)で操作できますが、\(U_2\)については、\(G\) において最も根に近い頂点がマージ後の木の根となるようにします。操作は\(O(log N)\)となります。UnionFind \(U_2\)を森として考えると、それぞれの連結成分の木の根が、連結成分のなかで\(G\) の最も根に近い頂点となっている状態です。

\(T = 1\) の場合

\(U_1\)で\(a, b\)が連結でない場合

\(U_1\)で\(a, b\)を連結にして終了します。

\(U_1\)で\(a, b\)が連結な場合

\(a,b\)のLCAを\(c\)とします。

\(a,b\)の間の頂点を\(U_2\)で連結にしていきます。\(a,c\)間と\(b,c\)間の頂点を連結にすればよいです。

\(a,b\)から一つずつ根に向かって遡ると\(O(N)\)かかってしまうため、全体で\(O(N^2)\)になってしまい間に合いません。

そこで、\(U_2\)での連結成分の根にジャンプすることにします。 ジャンプ後の頂点\(d\)が\(c\)よりも根から遠ければ、

• \(d\)とその親を\(U_2\)で連結にする
• \(d\)から根までの舗装されていない辺の数を管理するfenwick_treeやsegtreeでの入る/出るイベントの値を\(0\)にする。

と操作します。

辺が複数見られることはないので全体で\(O(N log N)\)で操作できます。

\(T = 2\) の場合

\(U_1\)で\(a, b\)が連結でない場合

\(-1\)を出力します。

\(U_1\)で\(a, b\)が連結な場合

fenwick_treeやsegtreeで「\(a\)と\(b\)の間の舗装されていない辺の数」を出力します。

計算量

\(O((N+Q)log N)\)