AtCoder Regular Contest 148 C問題 Lights Out on Tree

問題

$N$ 頂点からなる根付き木 $T$ は頂点 $1$ を根とし, 頂点 $i~(2 \leq i \leq N)$ の親は頂点 $P_i$ である.

各頂点には表裏のあるコインとボタンがある. ボタンを押すと, その頂点を根とする部分木にある全ての頂点のコインの表裏が入れ替わる.

次の $Q$ 個の問に答えよ.

問 $q$ : 頂点 $v_{q,1}, \dots, v_{q,M_q}$ にあるコインは全て表で, これら以外の頂点にあるコインは全て裏である. 適切にボタンを推し続けることによって, 全ての頂点にあるコインを表にできるか? また, 可能ならば最小何回押さなければならないか?

まず, 次のことがわかる.

よって, 操作の結果は各ボタンを押すか押さないかの状態によって決定される.

また, 次のことがわかる.

どんな初期状態からでも全てのコインを裏にできる.

(証明)

次のアルゴリズムによって実現できる.

このとき, 頂点 $v$ を見たあとは頂点 $v$ にあるコインの表裏が変わることはないから, 全ての頂点のコインが裏になる.

そして, 次のことも示せる.

状態が同じならば, 全てのボタンにおける「押す」「押さない」が一致する.

(証明)

「押す」「押さない」が一致しない頂点が存在するとする. その様な頂点のうち, 深さが最も小さい頂点のうち1つを選び, それを $w$ とする. このとき, $w$ の選び方から頂点 $w$ にあるコインの表裏が異なっている.

以上のことから, 次の2つが1対1に対応する.

よって, 全てのコインを裏にするための「押す」「押さない」の決め方は唯一存在するので, 次を求めてもよいということが分かった.

全てのコインを裏にするために,「押す」選択をしなければならないボタンの数

このとき, 初期状態において, 押すべきボタンは以下で挙げたものであり, これらで全部である.

これは頂点 $v$ とその親にある頂点におけるコインの表裏の一致関係を崩すためには頂点 $v$ を押すしか方法がないことによる.

よって求めるべきは以下の2つの和である.

この和はコインが表である頂点における (子の数 $+1$ ) の総和を $A$ , 両方の端点にあるコインが表である辺の数を $B$ としたとき, $A-2B$ と一致する.

$B$ については以下を満たす頂点 $v$ の数である.

よって, 1問あたり $O(M_q)$ 時間で求めることができ, 1テストファイルあたり木の情報を求める前計算と合わせて $\displaystyle O \left(N+\sum_{q=1}^Q M_q \right)$ 時間で求めることができた.