基本的な方針は，noshi91 さんによるこちらの記事に従い， Union-Find と頂点倍化を用いて二部グラフ判定を行う，という手法です．判定問題は，この手法をそのまま用いるだけで解けます．

黒に塗る頂点の個数の最小値を求めることを考えます．以下，頂点 \(x\) を白に塗る，に対応する頂点を \(x_w\)，黒に塗る，に対応する頂点を \(x_b\) とします．

Union-Find への辺の貼り方は，以下のようなものでした．

• 頂点 \({u_i}_w\) と頂点 \({v_i}_b\) の間に辺を貼る．
• 頂点 \({v_i}_w\) と頂点 \({u_i}_b\) の間に辺を貼る．

この辺の貼り方の性質により，連結成分の間の対称性が成り立ちます．すなわち，ある連結成分によって定められる色の塗り方に対し，それら全てを白黒反転させた塗り方に対応する連結成分が，必ず \(1\) 対 \(1\) に対応する構造になっています．

これにより，連結成分の集合を \(C = \{C_1, C'_1, C_2, C'_2, \dots, C_K, C'_K\}\) （\(C_*\) と \(C'_*\) は対応する連結成分）とし，\(C_i, C'_i\) の代表元を \({l_i}_w, {l_i}_b\) （このように代表元を決めることは，明らかに対称性により可能．また，\(C_i, C'_i\) のどちらの代表元が \({l_i}_w, {l_i}_b\) であるかは不問）とすると，頂点 \(y\) を含む連結成分における「黒に塗る，に対応する頂点」の数を \(b(y)\) として，黒に塗る頂点の個数の最小値 \(m_b\) は

\[m_b = \sum_{1 \leq i \leq K} \min(b({l_i}_w), b({l_i}_b))\]

となります．よって各連結成分ごとに \(b(y)\) の値を管理し，連結成分がマージされる際には \(m_b\) を差分計算することで，クエリに高速に答えることができます．

計算量は \(O(N + Q\alpha(N))\) となります．