Codeforces Round #382 (Div. 1) C: Ostap and Tree

http://codeforces.com/contest/736/problem/C

問題概要

木が与えられる。頂点を黒か白で塗りつぶす。どの白頂点も距離K以内に黒頂点があるような塗りつぶし方は何通りあるか。

• 1≦n≦100
• 0≦k≦min(20,n-1)

解法

dp[頂点][根から最も近い黒頂点の深さ][根から最も遠い黒に支配されていない白頂点の深さ]:=パターン数としてDPをする。

j+k'+1≦Kであれば右側の未支配頂点が消滅し、j'+k+1≦Kであれば左側の未支配頂点が消える。消えないならそのまま残る。

なかなか面倒なDP。結構バグらせてしまったので、Dに逃げたのはよかったかも。