公式解説の通りです。
実装の方針だけ。
- 任意の頂点pを選んで2回操作した場合もとに戻る
- 操作の順番が違っても結果は同じ
- 任意の頂点pだけを反転するには、頂点pにたいして操作をして、頂点pの子に操作する（戻す操作）で可能
- 以上により必要な操作の最小回数になる（厳密さを無視すると完成形からもう一回操作（打ち消す操作なので全体で-1）しても表が増えるので良くなることがない）（公式解説読んで）
よって、頂点とその子に対して操作をした回数を記録して、その和のmod 2をとった結果（2回操作すると元に戻る）の木全体の和が答え。
- 任意の頂点pの子に+1する操作を高速化したい
深さが2のような極端な木が与えられるとTLEするので、子の頂点に+1する操作を高速化する必要がある。
ある範囲に+1したいので、遅延伝播セグメント木が候補。
- ある頂点の子全体を配列の範囲で表したい
オイラーツアーのようなイメージだけど、オイラーツアーは部分木にたいする操作なので、BFSで辿った順番から頂点pの子の集合の範囲を決める。
- 遅延伝播セグメント木をどうするか
mod2 で任意の範囲に+1して、全体で和を取らないといけない。
範囲のサイズを一緒に持って、範囲に+1するときは、「次の状態の1数 = サイズ - その時の1の数」と更新することで、「1,0」の反転を表現できる。
（検索ワード: 範囲に+1 mod2 区間和）
- mod2で+1は範囲にxor 1と一緒
以上を実装してAC。
