题解 P1272 【重建道路】

貌似有的题解没有讲清楚 这里给出一点补充吧。 最常见的就是dp[i][j]为以i为根的子树，保留j个节点拆掉的最小边数。 可以发现题解中各种初始化和转移琳琅满目。 有的-1，有的-2. 其实就是因为dp状态没有讲清楚。 分着来说吧，dp[i][j]表示以i为根的子树，保留j个节点，且当前子树与父节点相连，拆掉的最小边数。 每个状态代表一棵子树，这个子树与父节点相连。 那么初始化的话dp[i][1]=son[i],一开始都是不连儿子只连父亲 那么转移的那个就变成了dp[u][j]=max(dp[u][j-k]+dp[v][k]-1) 为什么减1呢，因为注意到我们一开始点都是不与儿子相连的，我们通过dp的过程一步一步把他们连起来。 那么对于u->v这个边，一开始在初始化u的时候已经被减掉了，因为他是连接儿子的边，而v->u这个边并没有，因为这个连向父亲的边，我们要通过v转移，就得用u->v这个边，所以就得补回来。 而且最终算的时候，除了根节点无父亲外，其他的都要和父节点断开，也就是边数+1 第二种就是dp[i][j]表示以i为根的子树，保留j个节点，且当前子树不与父节点相连，需要拆掉的最小边数。 那么我们的初始化就变成了dp[i][1]=deg[i] 也就是把与i相连的所有边全部拆掉。 转移自然就变成了dp[u][j]=max(dp[u][j-k]+dp[v][k]-2) 和上面一样，因为u->v的边和v->u的边都已经在初始化的时候被减掉了，所以这时候要把他们连起来就得减去他们两个造成的贡献，也就是2. 那么答案就是dp[i][p] 这个就没有别的东西了，因为已经成为了一个独立的联通块了。 还有要注意的就是dp的范围。 当前节点必须保留，不然无法连接子节点。子节点的话也需要有一个，否则就不需要减去那点贡献了。 总的来说，dp还是要考虑合理性的