dp做题记录

树形 dp

• P3177 [HAOI2015] 树上染色

  初看此题时，dp 状态很明显是两维，但是合并子树时答案难于统计，然后……就不会了qwq。

  既然不通，考虑改变 dp 数组的含义，记 \(dp_{i,j}\) 表示当前 \(i\) 的子树中将 \(j\) 个点染黑对总答案的贡献。

  但是这样直接计算两点距离就变得更难了，考虑两点的路径统计，将统计相同颜色点两两之间的距离转化为统计每个边被计数的次数。于是我们每次进行转移时只需要考虑 \(i\) 到它的儿子 \(j\) 的边 \(e_{i,j}\) 对总答案的贡献，于是有 dp 方程：

  \[dp_{u,j}=dp_{u,j-k}+dp_{v,k}+e_{u,v}k(m-k)+e_{u,v}(siz_v-k)(n-m-siz_v+k) \]

  其中 \(n\) 为点的个数，\(m\) 为总的可以允许染成黑色点的个数，\(e_{u,v}\) 表示 \(u\) 到 \(v\) 边的权值，\(siz_u\) 表示以 \(u\) 为根的子树的大小，\(j\) 和 \(k\) 均为枚举的染黑点的个数。

  但是这样转移很明显是 \(O(nm^2)\) 的，于是我们在枚举每一个 \(m\) 时，给予 \(m\) 一个上下界限制，最大可能地去优化时间复杂度，于是有了 \(m\) 的限制：\(m\in[\max(0,j-siz_u+siz_v),\min(j,siz_v)]\)。

  可以证明，这样的时间复杂度是接近 \(O(nm)\) 的。

  代码。