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$ 的孩子中。

代码也非常的简单，可以见：