Codeforces 1324F Maximum White Subtree

正文索引 [隐藏]

题目传送门:Maximum White Subtree

题目大意

给你一颗无根树,其节点被染成黑白两色。对于其任意一个节点 v,我们要求出某一个包含 v 的联通块,使得联通块内白色节点 – 黑色节点数量最大。对于每一个节点,都输出最大化的差值是多少。

题解

这是一个树形DP,使用换根的操作实现比较简单。

假设,我们先不考虑对所有节点都求出答案,而是考虑针对 rt 节点求出答案。其实,这个问题很容易解决,可以使用一个简单的树形DP来做:以 rt 为根,我们自下而上的访问这颗树,并求以 x 为根的子树内,一定一定选择 x 的最大差值为 dp[x],转移则为:
dp[x] = \sum_{v~is~child~of~x} max(0, dp[v]) + cost[x]
可以理解为,计算 dp[x] 的时候,如果 x 的孩子节点 v 在答案中与 x 联通可以提供正向的差值贡献,那么就连上,否则丢掉。最终答案 rt 的答案存储在 dp[rt] 中,复杂度为 O(n)

如果,对于每一个节点都如此计算,复杂度为 O(n^2),显然不可以接受。于是,一个叫做换根的骚操作就诞生了:如果,我们可以将以 rt 为根计算出来的 dp_v[\cdots] 数组,使用较低的代价,变化成以 v_{rt}v_{rt}rt 的孩子节点)为根的 dp_{v_{rt}}[\cdots],那么我们就可以得到 v_{rt} 的答案 dp_{v_{rt}}[v_{rt}]。进一步,我们可以对这颗树进行中序遍历,并且在中序遍历的过程中,遍历到哪一个节点就把根换到哪一个节点,这样所有节点的答案都可以计算出来了。

对于本道题目,换根的代价是非常低的,因为 dp 数组是一个求和的形式,将根从 x 换到 v,无非就是顺序执行 dp[x] -= max(0, dp[v])dp[v] += max(0, dp[x]),即把 vx 的孩子中拿掉,再把 x 加入 v 的孩子中。

代码也非常的简单,可以见: