NOI 2021 Finals - Archaeologist
概要
Author : Cyanmond
制約が大ヒント。
解法
頂点には、まだ訪れていない場合$ 0が記入されている。また、もう訪れられない場合$ Lを記録することにする。そして、基本的にそれ以外の場合部分木に残っているまだ訪れていない葉の数を$ dとして$ \min(L - 1, d)を記録することにする。こうすると、うまく「もう訪れられない」という情報を上に伝搬させることができる。
適当にやるとうまくいかない。まだ訪れていない頂点が存在する場合必ずそこに行く、などのルールが必要。また、部分木がパスになっている場合は特殊処理が必要。