【CodeForces-1324F】Maximum White Subtree

题意#

给定一棵 $n$ 个节点无根树，每个节点 $u$ 有一个颜色 $a_u$，若 $a_u$ 为 $0$ 则 $u$ 是黑点，若 $a_u$ 为 $1$ 则 $u$ 是白点。

对于每个节点 $u$，选出一个包含 $u$ 的连通子图，设子图中白点个数为 $cnt_1$，黑点个数为 $cnt_2$，请最大化 $cnt_1 - cnt_2$。并输出这个值。

$1 \leq n \leq 2 \times 10^5$，$0 \leq a_u \leq 1$。

样例#

9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9

2 2 2 2 2 1 1 0 2

分析#

给每个点一个权值 $col_i$，白点 $col_i=1$，黑点 $col_i=-1$，问题转化为求包含 $u$ 的最大连通子图。

考虑换根 DP。

先随便定一个点作为根，不妨设为 $1$。在这棵有根树中定义状态。

设 $g_u$ 表示：在 $i$ 的子树中且包含节点 $i$ 的 最大连通块大小，转移显然：

只要子树答案 $>0$，就可以直接加上来。$\mathrm{father}_v$ 表示节点 $v$ 在以 $1$ 为根时的父亲。

接下来考虑换根的过程。

对于节点 $u$，如果以 $u$ 为根，那么还剩下 $u$ 连向 $\operatorname{father}_u$ 的这棵子树 没有统计进答案。

容斥。可以通过以 $1$ 为根，用整棵树减去 $u$ 所在的子树得到这棵子树。

设 $f_i$ 表示节点 $i$ 最终的答案。在处理节点 $u$ 时，我们希望已经计算出了 $f_{\operatorname{father}_u}$，其代表整棵树的信息。

用其减去第一遍 DP 时 $u$ 对 $\operatorname{father}_u$ 的贡献，就可以得到 $\operatorname{father}_u$ 的子树对 $f_u$ 的贡献了。

具体地，在有根树上，按照从根到叶子的顺序转移：

将父亲的答案消去自身影响后当成自己的子树，计算其对答案的贡献。

代码实现上，不必建立两个数组。注意第一次 DP 顺序是从叶子到根，第二次是从根到叶子。

代码#

void dfs1(int x, int fa) {
	for(int v : e[x]) if(v != fa) {
		dfs1(v, x);
		if(dp[v] > 0)
			dp[x] += dp[v];
	}
}
void dfs2(int x, int fa) {
	if(x != 1)
		dp[x] += max(0, dp[fa] - max(dp[x], 0));
	for(int v : e[x])
		if(v != fa) dfs2(v, x);
}