第4回 ドワンゴからの挑戦状 予選 D - ディスクの節約

問題
提出コード
なんかこの問題の解説すごくむずかしいですね

解法

Nの制約が少ないので、現在のメモリの状態に対していろいろすることを考えます。ということで、bitDPです。
2進数に対し、小さい桁から順番に頂点の番号を割り当てていきます。
例えば、101だと、頂点1と3が書き込まれたような感じです。
dp[S] = 状態Sになるような、タスクの処理の手順のうち、"必要最大ディスク量"の最小値
とすると、答えはdp[1]となります。ここから、何も存在しない初期状態に向けて戻してあげることを考えます。
また、有向木の葉の部分のみがディスクにあるような状態(立っているビットが1つのみの場合)のdpの中身は、その頂点のディスク量そのものになるので、あらかじめ初期化をしておきます。
さて、ある状態Sになるには、そのSの中の頂点を1つ選び、その頂点の子すべてと置き換えてあげる作業が必要になります。
置き換えた後の状態をTとします。
ここで、必要最大ディスク量は、ある手順でSから初期状態に戻した時、その手順の中で最も大きかったディスク量になります。
すると、dp[S]は次のように書くことができます。
dp[S] = min{ max(Sから選んだ頂点とTに含まれる全ての頂点のディスク量の総和, dp[T]) }
Sから状態Tにうつるときに一番使用ディスク量が増える瞬間は、Tに含まれる頂点とTにうつるために選んだ頂点が同時に存在するときです。その後の手順についてはdp[T]を見れば最大使用量がわかるので、その二つのうち大きな値をとれば、SからTに遷移したと仮定したときの最終的な必要ディスク量がわかります。
これをすべてのTに対して調べて、最小値をとればよいです。
ということで、この遷移を繰り返すと、答えを求めることができます。