AtCoder AGC 014 B: Unplanned Queries

性質を満たす木が存在する必要十分条件は、すべての頂点についてクエリに現れた回数が偶数であることである。

(1)すべて偶数回の出現だった場合

すべてのクエリについて

辺(a[i], b[i])で2頂点をつなぐ。ただし、a[i], b[i]がすでに同じ連結成分内にある場合はこのクエリを無視。

最終的にできた森から適当に木を作れば、性質を満たしている。

(2)奇数回現れる頂点がある場合

根付き木を考える。

mod 2のもとで

クエリ(u, v)は

(u, root), (v, root)

に分解できる。

奇数回現れる頂点のうち最も深いもの1つを頂点uとする。

頂点uを端点とするパスによってuとその親pをむすぶ辺(u, p)は奇数になっている。辺(u, p)の数を偶数にしたい。

そのために、uの子孫のうちuを除く頂点(その集合をSとする)の出現回数が合計で奇数でなければならない。しかし、そうなると奇数回現れる頂点でuより深いものが存在することになり矛盾する。よって、辺(u, p)の数は奇数になる。