ABC246 G - Game on Tree 3 (600)
コンテスト中の考察
二分探索で取り得る最大値を探索する
二分探索で目的にしている値未満の値は塗りつぶさなくて良くなる
DFSで解く
子の中で閾値以上のは全部塗りつぶさないとそこに進まれるので駄目
それぞれの子について残りの塗りつぶし回数で達成できなければ達成可能
解説の解法
DFS時にその時点で塗り替えしておかないといけない数を返すようにする
スタート時にこれが0でなければ達成可能
0ならそのように塗りつぶしておけるので達成不可能a
DFSは$ \mathcal{O}(N)でできるので全体で$ \mathcal{O}(N \log A_{max})