ARC148 C - Lights Out on Tree (500)
愚直に考えるとクエリ毎に木の根から表向きの頂点を裏向きにしていけば良い
これはクエリ毎に木全体を見るので$ \mathcal{O}(NQ)
クエリ毎に以下を行う
新たな辺情報の配列を持つ
それぞれの表向きのコインについてその親にそのコインへの辺を追加
根でその親が無い場合は除外
親が表では無い表のコインについてそれぞれDFSを行う
親も表ならそちらのDFSで探索済みなので飛ばす
DFSではその点がひっくり返された後という想定で解いていく
今見ている点の子で元々が裏のコインはそれらをそれぞれもう一度ひっくり返せば良い
これに必要な回数は$ 元々の辺の数 - 新たな辺情報での辺の数
子で元々表のコインについては今見ている時点で反転されているのでそのままDFSをすればよい
最初に見た点をひっくり返す1回を忘れないように注意
クエリ数に依らず$ \mathcal{O}(N + \sum M)にできる