CODE THANKS FESTIVAL 2018 F-Coins on the tree

本番は誤読をした...。

問題

F - Coins on the tree

解法

　辞書順最小を作れという指示がある。辞書順最小ということは，前の数字が小さいことが正義である。ならば，先頭から「1にできるか？」を判定し，できるなら確定，できないなら「2にできるか？」ということを判定，というように貪欲に試していこうという方針は自然である。

　それでは，試しに番目のコインを頂点に置けるかということを判定することを考えよう。まず，コインを頂点に置いたのだから，木の根からの距離を(ただし，とする)とすると，手数をだけ消費する。ここから，残りの枚を，手でピッタリ置ききる必要がある。このようなことが可能であるの条件がわかればよい。
　まず，に置くと決めたら，の子孫たちはもう使えないことに注意しよう。つまり，1番目のコイン以後に使える頂点の数が減るのである。このとき，もし使える頂点の数がを下回るようなことがあれば，1番目のコインをに置くことはできない。
　使える頂点の数はクリアしたとして，手数の問題を考える。残り手数をピッタリ消費する，という条件は扱いにくいが，このような場合は可能な手数の上限と下限を考えるとうまくいくことがある。まず，手数の上限は，到達可能な頂点のうち，を大きい順に個取ったときの和である。消費する手数をできるだけ多くするには，できるだけ根から深いところにコインを置くようにすればよいので，このことがわかる。同様に，手数の下限は，を小さい順に個取ったときの和である。理由は上限と同様である。そして，この上限と下限の間の手数の消費は必ず可能である。手数の下限の状態から，手数の上限の状態までコインを順番に動かすことを考えれば，このことがわかる。以上より，がこの上限と下限の間にあれば，コインを頂点に置くことが可能となる。
　この判定は高速にできるだろうか。高速といっても，本問ではくらいかけてよい。それならば，到達可能な頂点をすべて訪問し，のリストを作る。リストのサイズがより大きいことを確認した後，これらの大きいほう，そして小さいほうからの和をそれぞれとり，と比較すればよい。sortを使ってもでできる。
　1番目のコインをに置くことが可能だとわかったら，をだけ減らし，2枚目のコインについても同様にどの頂点に置けるかを番号の小さい順に調べる。このようなことを繰り返せば，辞書順最小のコインの置き方が求まる。もし，あるコインがどの頂点にも置けないということであれば，を出力すればよい。

以上をまとめて，次のようにすればこの問題が解ける。

1. 最初に，各頂点についてを求める。
2. 番目のコインを頂点に置けるか，ということをが小さい順に試す。到達可能な頂点を訪問しながら，のリストを作って，判定を行う。置ける条件は，①のリストのサイズが以上であること かつ ②の小さいほうから個の和を，大きいほうから個の和をとすると，であること の2つ。ただし，このは番目のコインを置こうとしている時点での残り手数を表している。頂点に置けるとわかれば，をだけ減らして，次のコインに進む。置けないなら，次の頂点を試す。どの頂点にも置けないとなれば，を出力して終わり。
3. 枚目のコインまで置けたら，結果を出力して終わり。

全体の計算量はである。

実装

Submission #4123308 - CODE THANKS FESTIVAL 2018
dfsが3つあるが，それぞれの役割は以下にようになる。

• :を計算する関数。
• :判定パートで，到達可能な点を訪問する関数。というのは，それがtrueのときに頂点にはコインを置けないということを表してる。頂点を訪問したら判定用のリストにを追加する。の子がまたはがtrueなら，その子孫はもうコインが置けない頂点なので，その先には訪問しない。
• :ある頂点にコインを置くと決まった後，の子孫にはもうコインは置けないということを記録しに行く関数。頂点番号の小さい順から試すということをするため，この作業を怠ってはいけない。

判定パートが若干混乱するが，整理すると綺麗な問題だなあと思う。