题解：CF735E Ostap and Tree

· · 题解

限制相当于对于每个点 i，离 i 最近的染色点距离不超过 k。

对于每个 i，考虑记 d_i 表示离 i 最近的染色点距离，考虑每一组 d_1,d_2,\cdots,d_n 至多对应一种染色方案，每种染色方案也恰对应一组 a，故考虑对可行的 d 计数。

什么样的 d 存在一种对应的染色方案呢？充要条件是：

  1. 相邻两个的 d 差值不超过 1。
  2. 对于所有 d_u \neq 0，存在邻点 v 使得 d_v = d_{u}-1。

必要性容易证明，充分性考虑对于 d 的值从小到大归纳。

于是可以直接 DP，记 f_{i,j,0/1} 表示以 i 为根子树，d_i = j，是否存在 i 的儿子 v 使得 d_v = j - 1，转移是容易的，复杂度 O(nk)。