Codeforces Round #635 (Div. 2) C. Linova and Kingdom
C. Linova and Kingdom
問題概要
頂点を根とする頂点数
の木がある。最初、頂点の色はすべて白の状態から、
個の頂点を黒く塗る。黒色の点から、根までの最短路で、白の点を通る数を最大化したい。塗り方を適切に決めたとき、最大値を求めよ。
制約
解説
まず小さい具体例から考えます。以下のような木のとき、すべて白色の状態から、どこを塗るべきかを考えると
最も根から遠い頂点を塗るべきだとわかります。このことから、根から遠いところを貪欲に塗っていく方法がよさそうだとわかります。このときスコアはです。
では、次に塗るべきはどの頂点でしょうか？直感的に、頂点か
になりそうです。実際に塗って計算してみると、スコアはそれぞれ、
となり、頂点
の方がスコアがいいことになります。
ここまでの実験から得られる洞察として、
- 同じ深さでも、スコアに差が出る
- 葉に近い方から塗った方がいい
ということがわかります。よって、深さのみで貪欲をすることができません。また、二つ目の、「葉から近い方から塗った方がいい」というのを、簡単に証明してみます。
以下のような頂点以下の部分木のサイズが
であるような木を考え、すでにこの部分木はすべて黒で塗られているとします。
すると、に塗った場合と、
に塗った場合、スコアはそれぞれ
、
になり、
に塗る方がいいことがわかります。この実験結果から、ある頂点を塗ることによってスコアの変動は、その頂点の深さ - その頂点以下の部分木に含まれる黒の頂点の数になることがわかります。部分木に含まれる黒の頂点の数は不変であることから、深さを最大化すればよいことがわかります。よって、常に下と間を開けることは無駄で、間を開けない方が得をすることがわかりました。
葉の方向に詰める貪欲をしていいことはわかりました。では、詰まっている場合に、複数ある頂点からどの頂点を優先的に選ぶべきでしょうか？
これは、先ほど証明の過程で出てきた特徴量が鍵を握ります。深さ - 部分木に含まれる黒の頂点の数というものでしたが、今の簡単な証明から、頂点以下の部分木は必ず黒で塗られているので、深さ - 部分木に含まれる頂点の数の大きい順に塗っていけばいいことがわかります。これらの頂点に関する特徴量は、DFSやBFSによって求めることができるので、で解くことができました。
- 今の流れで納得できない人へ
今のある頂点を縫ったときにスコアの変動がイメージつかない、思いつかないという方は、以下のようなもっと極端な木を考えてみるといいかもしれません。小さい例について考えながら、たまには極端な方向へ旅をしてみるのもいいかもしれません。
