CF1324F Maximum White Subtree

看到题目最直接的想法就是以每个节点为根进行 n n n 次树形 d p dp dp。因为以节点 u u u 为根时我们只需要考虑把树的某些"分杈"剪去，而不用关心 u u u 节点是否被包含在某个子树中。

但时间复杂度是 O ( n 2 ) O(n^2) O(n2)，所以考虑换根 d p dp dp。

换根 d p dp dp

1. 若一个节点是黑色，那么就让 c o l [ i ] = − 1 col[i] = -1 col[i]=−1，不然就让 c o l [ i ] = 1 col[i] = 1 col[i]=1。

2. 以 1 1 1 为根 d f s dfs dfs 求出每个节点答案的"一部分"（真正的答案来自每个节点的所有子节点与它的父节点，这里"一部分"是指构成每个节点正确答案的子节点部分）。很显然转移方程为：
   d p 1 [ u ] = c o l [ u ] + ∑ v ∈ s o n [ u ] m a x ( 0 , d p 1 [ v ] ) dp1[u] = col[u] + \sum_{v \in son[u]}{max(0, dp1[v])} dp1[u]=col[u]+v∈son[u]∑​max(0,dp1[v])
   之所以 d p 1 [ v ] dp1[v] dp1[v] 要与 0 0 0 取 m a x max max 是因为若这部分子树贡献为负数，我肯定会把它"剪去"。

3. 再次 d f s dfs dfs 进行 d p dp dp，进行换根。转移方程为：
   d p 2 [ u ] = d p 1 [ u ] + m a x ( 0 , d p 2 [ f a ] − m a x ( 0 , d p 1 [ u ] ) ) dp2[u] = dp1[u] + max(0, dp2[fa] - max(0, dp1[u])) dp2[u]=dp1[u]+max(0,dp2[fa]−max(0,dp1[u]))
   f a fa fa 为第一次 d f s dfs dfs 中， u u u 的父节点。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e5 + 7;
const int inf  = 0x3f3f3f3f;

int n, col[maxn];
vector<int> e[maxn];
int fa[maxn];
int dp1[maxn], dp2[maxn];
void dfs1(int u, int f) {
	fa[u] = f, dp1[u] = col[u];
	for (int v : e[u]) {
		if (v == f) continue;
		dfs1(v, u);
		dp1[u] += max(0, dp1[v]);
	}
}
void dfs2(int u, int f) {
	dp2[u] = max(0, dp2[fa[u]] - max(0, dp1[u])) + dp1[u];
	for (int v : e[u]) {
		if (v == f) continue;
		dfs2(v, u);
	}
} 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
    	int v; scanf("%d", &v);
    	if (v) col[i] = 1;
    	else col[i] = -1;
	}
    for (int i = 1; i < n; ++i) {
    	int u, v;
    	scanf("%d%d", &u, &v);
    	e[u].push_back(v);
    	e[v].push_back(u);
	}
	dfs1(1, 0);
	dfs2(1, 0);
	for (int i = 1; i <= n; ++i)
	    printf("%d ", dp2[i]);
	return 0;
}