以下の解法について考えます。

---

• 隣接頂点を unordered_set で持つ隣接リストと、各頂点の連結状態を持つための Union-find を用意する。…(1)
• タイプ 1 のときは、隣接リスト / Union-find のそれぞれに辺を追加する。…(2)
• タイプ 2 のときは、頂点 \(a,b\) について、
  • 2 点が非連結なら \(0\) を返す。（Union-find を用いる）…(3)
  • そうでない場合、以前に同様の質問をしていた場合は（結果が変わっていることはないため）その時の答えを返す。…(4)
  • そうでもない場合、次数が小さい方の頂点に隣接する頂点すべてについてもう一方の頂点に隣接しているか判定し、隣接しているものがあればその頂点番号を、なければ 0 を返す。（隣接リストを用いる）…(5)

結論から言えば、この解法は \(O(N + Q\sqrt Q)\) 時間で動いています。具体的には、(1) で \(O(N)\) 時間、(5) で \(O(Q \sqrt Q)\) 時間かかり、この 2 つの工程がボトルネックとなっています。
(1)~(4) の計算量の解析は容易にできるものとして、(5) の計算量解析を以下に書きます。

---

証明：
頂点 \(i\) についての最終的な次数を \(d_i\) とします。また、 \(i\) 番目の (5) の工程で質問されるクエリの 2 頂点を \((a_i, b_i)\) とします。ここで、このクエリで探索される頂点数は高々 \(\min(d_{a_i}, d_{b_i})\) 個であることに注意してください。

探索する頂点数の全体を通じての合計 (\(=S\)) を最大化するように \(d,a,b\) を決めることを考えます。この際に、

• \(d\) は広義単調減少である。
• \(a_i < b_i\) である。

という 2 つの条件を加えても一般性を失いません。すると、 \(i\) 番目のクエリでは高々 \(d_{b_i}\) 個の頂点を探索することがわかります。

条件を緩和し、ちょうど \(d_{b_i}\) 個の頂点を各クエリで探索するものとすると、 \(b_i\) の小さいクエリを多く入れた方が探索個数が増えます。

そうすると \((a_1 , b_1), (a_2, b_2), (a_3, b_3), (a_4, b_4)\cdots = (1,2), (1,3), (2,3), (1,4) \cdots\) とするのが最適です。この場合に、 \(b_i >\sqrt{2Q}\) となる \(i\) は存在しないことに注意してください。

ここで主客転倒を用います。各頂点 \(i\) について、 \(b_j = i\) を満たすクエリ \(j\) すべてに対しての探索個数の合計値 \(s_i\) を考えます \((\sum s = S)\) 。

\(d\) の総和が \(2Q\) 以下であることと \(d\) の単調性に留意すれば、 \(d_i \leq \frac{2Q}{i}\) です。また、 \(b_j = i\) なる \(j\) の個数は高々 \(i\) 個であるため、 \(s_i \leq 2Q (=\frac{2Q}{i} \times i)\) です。

さらに、 \(b_i >\sqrt{2Q}\) となる \(i\) は存在しないことを用いれば、 \(s_i\) が正となる \(i\) の個数は \(\sqrt{2Q}\) 個以下であることもわかるため、 \(\sum s \leq 2Q\sqrt{2Q}\) です。これは求めるべき答えです。

---

よって、この問題を \(O(N+ Q\sqrt Q)\) 時間で解くことができました。

なお、この解説と同様の考え方を用いる問題として、JOIsp2024 4-1 (https://img.atcoder.jp/joisp2024/escape2.pdf) が挙げられます。