Codeforces Round 864 (Div. 2)

　Cまで三完。ARCの直後ということもあり、遅刻して今一つやる気が出ないままやっていたが、それとは関係なくDが分からなかった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 864 (Div. 2) D分からず。
A 端や角にあるかチェック
B 対称な地点と色が違うかをチェック。nが奇数なら、中央の色を変えれば良いが偶数ならmod 2の条件が必要
C 左上と右下を調べると、「候補が二点」か「候補がある行（列）」になる。後者でx行目にあるなら(x,1)と聞けば良い。

— titia (@titia_til) April 8, 2023

D. Li Hua and Tree

　解法ツイートを見たら、愚直にやっても、三点更新くらいで済むのでできるらしい。

　このヒントを見てAC。

　ちゃんとクエリ2の様子を図に描いて観察すれば、子供の数も、子孫の重要度の和も高々三点しか更新されないことは分かったはず。これに気付かなかったのはやる気がなかったとしかいいようがない。反省。

　あとは実装問題。こちらは結構難しいし面倒くさい。

　heapqに（子孫の個数, index）を入れて管理したが結構制限時間ギリギリだったし、どんな情報を持ち、何を更新しなくてはいけないかも整理できておらずWAを出してしまった。