まず各頂点に \(2^{A_v}\) が書き込まれているものとして、操作を以下のように言い換えます。

• 両端点に書き込まれている値 \(x\) が等しいような辺を選んで縮約操作を行う。縮約により生じる新たな頂点には \(x+x=2x\) を書き込む。

この言いかえの下で考えると、 \(T\) に操作を行うことで \(1\) 頂点からなる木にできる場合、その \(1\) 頂点に書き込まれている値は \(\sum 2^{A_v}\) に等しいです。よってこの値が \(2\) のべき乗に等しいことが必要です（とくに、 \(2\) のべき乗でない場合はすべてのクエリに対する答えはNo になります）。以降、上の条件は満たされているものします。

部分点解法で述べた事実について復習しましょう。 \(T\) を \(1\) 頂点からなる木にできるかについて、以下が成り立ちます。

\(k=1,2,\dots\) の順に、 \(2^k\) が書き込まれている頂点からなる誘導部分グラフが完全マッチングをもち、縮約し続けて最終的に \(1\) 頂点になることが答えが Yes である必要十分条件である

このことに基づいて実際に縮約をシミュレーションして判定を試みると最悪 \(\Theta(NQ)\) 時間かかってしまいます。

これを解決するために、完全マッチングの存在判定をより単純化しましょう。以下の事実が成り立ちます。

白、または黒の色がついている \(n\) 個の頂点からなる根付き木 \(T\) について、黒い頂点の数を \(f(T)\) 、頂点 \(v\) を根とする部分木内の黒い頂点の数が奇数であるような \(v\) の数を \(g(T)\) とおく。このとき、 \(\lfloor \frac{f(T)+1}{2} \rfloor \leq g(T)\) が成り立ち、等号が成立するのは \(T\) において黒い頂点からなる誘導部分グラフが完全マッチングを持つときである。

これは帰納法により示すことができます。これを用いると各 \(k\) について、

• \(2^1,2^2,\dots,2^{k-1}\) が書き込まれている頂点について縮約を行って得られる木において、\(2^k\) が書き込まれている頂点の数
• \(2^1,2^2,\dots,2^{k-1}\) が書き込まれている頂点について縮約を行って得られる木において、頂点 \(v\) を根とした部分木であって、 \(2^k\) が書き込まれている部分木内の頂点の数が奇数であるような \(v\) の数

の \(2\) つの値が求まれば判定ができます。

まず前者についてですが、各レベルの頂点の数の変化は実際に縮約を行わずとも頂点数だけ見れば \(O(N)\) 時間で計算できます（さらに、前者の値についてはクエリにより変化しません）。

つぎに後者についてです。条件を満たす頂点 \(v\) を根とした部分木内の頂点に書き込まれている数の総和について考えると、 \(2^1,2^2,\dots,2^{k-1}\) が書き込まれた頂点は部分木内になく、 \(2^k\) が書き込まれている頂点は奇数個であるため、 総和の最下位bitは \(2^k\) になります。総和は縮約により変化しないので、木 \(T\) において計算し最下位bitに着目することで、各 \(v\) がどの \(k\) に対して寄与するかが計算できます。

ここで、後者の値の計算では非常におおきな数の和や最下位bitを計算する必要がでてきます。これについて、まず各頂点のレベルが固定されている場合から考えます。この場合は数そのものの代わりに、数を二進法表記した際に立っているbitの集合をstd::set などで管理すると、weighted union heuristic を用いることで \(O(N\log^2 N)\) 時間で計算することができます。繰り上がり処理については全体で \(O(N)\) 回しか発生しないので愚直に処理していいです。

最後にswapクエリがある場合の処理ついて考えます。swapクエリにより部分木内の頂点に書かれている値の総和が変化するような頂点は \(1\) つだけ（ \(u_{e_i}, v_{e_i}\) のうち、葉側のほう）です。よって、このような頂点における総和の最下位bitの変化が計算できればいいです。各頂点に対し、総和の立っているbitの集合を保持してクエリ処理を行うと空間計算量が最悪 \(\Theta(N^2)\) になってしまうため、 \(v\) を根とする部分木での総和の初期値が得られたタイミングでクエリによる変化を計算することにします（計算後にクエリによる変化を逆順にたどって初期状態に戻します）。ここで問題になることとして、総和の変化は \(+2^k\) という変化だけでなく、 \(-2^k\) という変化もありうるため、立っているbitの集合を管理し、繰り上がり・繰り下がりを愚直に処理すると、最悪計算量が \(\Theta(N^2\log N)\) になってしまう点があげられます。これは、立っているbitの集合ではなく、立っているbitのrunを管理する（例えば \(2^1+2^2+2^3+2^5+2^6\) であれば \(\{[1,3],[5,6]\}\) という形で管理する）と、いずれのクエリも \(O(\log (N+Q))\) 時間で処理できるようになり、解決します。

以上よりこの問題を \(O((N+Q)\log^2 {(N+Q)})\) 時間で解くことができます。