AtCoder Grand Contest 012 B: Splatter Painting
http://agc012.contest.atcoder.jp/tasks/agc012_b
解法
di が小さいのが鍵に見える。
dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。
補足
ある頂点から距離 d の範囲を塗りつぶすという命令は、距離 d-1 の塗りつぶし命令に分解できる。
頂点 v から距離 d の塗りつぶし命令が複数あるならば、最も新しい命令以外は無視しても良い。無視することにより計算量は O(d(n+m)) になる。