F. 树染色方案计数
一道很有意思的树形 dp，和 P4516 潜入行动 非常相似。
考虑状态怎么定义。第一个维度肯定是以 \(i\) 为根的子树，第二个维度是当前子树中的特殊节点个数，同时还要考虑当前节点的颜色，即为第三个维度。
当前节点的颜色无非跟 \(k\) 有关，即小于 \(k\)，等于 \(k\)，大于 \(k\) 这三种关系，将这三种关系记为 \(0/1/2\)。故定义 \(dp_{i,j,k}\) 表示以 \(i\) 为根的子树中有 \(j\) 个特殊节点，且当前节点颜色编号关系是 \(k\) 的染色方案数。
考虑初始化。\(dp_{i,0,1}=k-1,dp_{i,1,1}=1,dp_{i,0,2}=m-k\)。
考虑转移。套路的来讲，若 \(x\) 是 \(y\) 的父亲，则枚举 \(x\) 选择 \(j\) 个点，枚举 \(y\) 选择 \(k(k\leq j)\) 个点。即为 \(dp_{x,j}= \text{combine}(dp_{x,j-k},dp_{y,k)}\)。
此题中，因为加上了 \(k\) 这个维度，所以需要讨论 \(k=0/1/2\) 这三种情况。
- 若 \(k=0\)，即当前节点颜色编号小于 \(k\)，则儿子随便选。
\(dp_{u,j,0}= \sum dp_{u,j-k,0}\times (dp_{v,k,0}+dp_{v,k,1}+dp_{v,k,2})\) - 若 \(k=1\)，即当前节点颜色编号等于 \(k\)，则儿子颜色编号只能小于 \(k\)。
\(dp_{u,j,1}= \sum dp_{u,j-k,1}\times dp_{v,k,0}\) - 若 \(k=2\)，即当前节点颜色编号大于 \(k\)，儿子颜色编号除了 \(k\) 其他都可以选。
\(dp_{u,j,2}= \sum dp_{u,j-k,2}\times (dp_{v,k,0}+dp_{v,k,2})\)
答案即为 \(\sum_{i=0}^{x}\sum_{j=0}^{2 } dp_{1,i,j}\)。
代码：code