Codeforces 855-C 树形DP

September 26, 2017

题意 # 给一颗树， 每个结点可以标记一个type。 一共有m种type，分别是1-m。 其中有一种特殊的type，编号为k，要求： 在这棵树中，最多出现x个type为k的点。 每个type为k的点，其相邻的点type必须小于k。 问，给定以上数据，求树的标记种类数有多少。 数据范围： n <= 1e5, x <=10, m <=1e9 分析 # 这是一个典型的树形DP，DP的维度应该至少是3维。 Dp[i][j][z] 表示： 以i为根的子树，用掉z个k时的种类数。 其中对于根结点的type选取，分三种情况， 0：type < k (type >=1 ) 1：type = k 2：type > k (type <= m) Dp表示内容确定以后，就要来找转移方程了。 这种组合种类的问题，只要分清楚哪些量之间是相乘的关系，哪些量是相加的关系就好办了。 思考一种普遍的情况，对于一个根节点和其儿子节点之间的关系，以及儿子之间的关系。 可以确定的是，各个儿子之间的关系是相乘的关系。因为儿子之间是没有约束的，不直接相连就没有type < k的约束。所以每个子树内的排列种类是直接乘到贡献中的。 然后就是儿子与父亲节点的关系。 讨论一下，如果父亲的取值是0类型，也就是type < k。 对于任何一个儿子都可以任意选择type，并且这些选择之间是相加的关系。选择之和与父亲的选择种类之间是相乘关系。 总上，父亲与儿子、儿子与儿子之间都是相乘的关系，儿子内部是相加关系。 这个时候我们可以选择将父亲先放在一边，先合并各个儿子。最后把合并后的儿子与父亲合并。 为什么不能直接把儿子合并到父亲上呢？ 因为对于一个固定的z来说，其对应的情况是z个k在所有子树中的全排列种情况。这些排列又是相加的关系，很显然我们不能去求这个排列，复杂度太大。 我们要在处理每个儿子的时候，将其对不同的z的贡献都存起来，这个我们可以做到。 以下的代码以根为0时举例，其他两个情况一样。 for(int j=0; j<=x ;j++){ for(int z = 0; z <= x; z++){ if(l+z > x) continue; Dp[u][0][j+z] += ta[0][j] * (Dp[v][0][z] + Dp[v][1][z] + Dp[v][2][z]); } } ta[0][j] 记录的是在当前儿子之前的所有儿子中，使用了j个k时，所有的种类数。 其中，Dp[u][0][j+z] 记录的是对于当前儿子结点v，使用了j+z 个k时，所有的种类数。 ...