\(v\) を固定したときを考えてみます。これは、以下の問題に帰着されます。

長さ $N$ の整数列 $A,B$ が与えられます。各 $i(1 \le i \le N)$ に対して、$A_i$ か $B_i$ のどちらかを選び、選んだ整数の種類数を最大化してください。

この問題は、\(N\) 頂点グラフを用意して、\(1 \le i \le N\) に対して \(A_i\) と \(B_i\) を結びます。そして、それぞれの連結成分に対して \(\min(\)辺の数,頂点数\()\) を足し合わせたものが答えとなります。

これを全ての頂点 \(v\) に対して行っていては、計算量が \(\mathrm{O}(N^2)\) かかってしまい間に合いません。そこで、UnionFind を用いて少し改造します。

頂点 \(1\) から dfs をして、\(A_i,B_i\) 間に辺を貼ったり削除したりすることを考えます。ただし、削除する辺は dfs であるため直前に貼った辺であることに注意してください。なので、前回貼った辺で変わった unionfind の情報を全て元に戻せばよいです。

データとしては通常の unionfind(各連結成分の size、親) に加えて、各連結成分の辺数、そして連結成分に対する \(\min(\)辺の数,頂点数\()\) の総和を持ちます。さらに、辺削除に対応するために \(i\) 回目のクエリで変わったデータと、その変わる前の値も全て持っておきます。

辺を結ぶクエリの際は、通常の unionfind のようにサイズが大きい方の連結成分に小さい連結成分をくっ付けます。ここで、変わったデータを全てまとめて持っておく必要があります。 \(\min(\)辺の数,頂点数\()\) の総和の更新も行います。計算量は経路圧縮をしないため \(\mathrm{O}(\log N)\) となります。

辺を削除するクエリは、前回のクエリで変わったデータを全て戻せばよいです。このデータの個数は定数個であるため、このクエリは定数時間で処理することが出来ます。

よって、全体で \(\mathrm{O}(N\log N)\) でこの問題を解くことが出来ます。