SRM622Div1Medium

問題

ノード数Nのツリーが与えられる。ツリー内部のノード同士の距離がDを超えないように、K個のサブツリーを構築する。最小のKを求めよ。

解法

メモ化と再帰を用いて解く。f(x, d)はノードxをルートとした時の最小のサブツリーの数を返す。xはノードの番号、dは進むことが可能な深さを示す。ノードxをルートとした時のサブツリーは以下の条件を満たす。

xからリーフまでの最長距離がD以下
サブツリー内のノード内の距離がD以下

ノードxの子であるノードyを選び、サブツリーの最大深さをMと仮定する。ノードyに対してはf(y, M-dy)でサブツリーの数を探索する。dyはxからyまでの距離を示す。次に、ノードxの子であるノードzがノードyを含んでサブツリーを構築できるかを調べる。この時、満たす必要がある条件は

xからリーフまでの最長距離がM以下
サブツリー内のノード内の距離がD以下

ひとつめは、最大深さをMと仮定しているからである。
これらの条件を式にすると
$min(M, D-M)$
となる。
ノードxからノードzまでの距離dzが以下の式を満たす場合は、
$dz \leq min(M, D-M)$
f(z, r - dz)を探索する。rはmin(M, D-M)である。
Mについて全探索することで解を求めることができる。