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])$,即把 $v$ 从 $x$ 的孩子中拿掉,再把 $x$ 加入 $v$ 的孩子中。

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