A91496.最大颜色子树 解题思路

问题分析

这是一道树形DP + 换根DP问题。每个顶点的颜色可以映射为权值：

• 白色（a_v = 1）→ 权值 +1
• 黑色（a_v = 0）→ 权值 -1

问题转化为：对每个顶点 v，在所有包含 v 的连通子图中，求最大的权值和。

关键点：

• 子树（连通子图）不一定是原树中以某个节点为根的子树，而是任意连通子图
• 必须包含指定顶点 v
• 需要在 O(n) 或 O(n log n) 内完成

核心思路

对于固定的顶点 v，包含 v 的最大权值连通子图等价于：

• 选择 v 本身（必须选）
• 对于 v 的每个邻接方向（即每条边连接的分支），可以选择是否将这个分支的一部分加入

实际上，这与"最大子段和"在树上的推广类似。

第一步：任选根，做第一次DFS（树形DP）

以 1 为根，定义：

• dp_down[u]：在以 u 为根的子树中，包含 u 的连通子图的最大权值和

转移方程：

dp_down[u] = w[u] + Σ max(0, dp_down[child])

其中 w[u] 是 u 的颜色权值（+1 或 -1）。

这表示：u 必须选，对于每个孩子分支，如果孩子那边"包含孩子的最大连通子图"权值为正，则加入；否则不选该分支。

第二步：换根DP（第二次DFS）

对于每个节点 u，我们还需要考虑父节点方向的分支。

定义：

• dp_up[u]：以 u 为根的子树之外的部分（即整棵树去掉 u 的子树后，包含 u 的父节点方向的连通子图）的最大权值和

或者更直接地，我们需要计算每个节点 v 的答案：

ans[v] = w[v] + Σ max(0, 所有方向上的 dp[方向])

其中"所有方向"包括：

1. 每个孩子方向：dp_down[child]
2. 父节点方向：需要额外计算

所以我们需要计算每个节点从父节点方向能获得的最大贡献。

设 f[u] 表示：从 u 的父节点方向，能贡献给 u 的最大权值和（不包含 u 本身）。

那么：

f[child] = max(0, w[u] + Σ max(0, dp_down[other_children]) + f[u])

其中：

• w[u]：父节点 u 本身的权值
• Σ max(0, dp_down[other_children])：u 的除 child 以外的其他孩子方向的正贡献
• f[u]：u 的父节点方向的正贡献
• 整体再与 0 取 max，因为 child 可以选择不连接父节点方向

这样，每个节点 u 的答案就是：

ans[u] = w[u] + Σ max(0, dp_down[child]) + max(0, f[u])

算法步骤

1. 构建树：邻接表存储
2. 第一次DFS（后序遍历）：
   • 计算 dp_down[u] = w[u] + Σ max(0, dp_down[child])
3. 第二次DFS（前序遍历）：
   • 计算每个节点的 f[child]
   • 计算每个节点的答案 ans[u]
4. 输出答案

复杂度分析

• 时间复杂度：O(n)，每个节点和边被访问常数次
• 空间复杂度：O(n)

注意事项

1. 权值映射：白色 a=1 → +1，黑色 a=0 → -1
2. 对于叶子节点，dp_down[leaf] = w[leaf]（可能为 -1）
3. f[根节点] = 0（根节点没有父节点方向）
4. ans[v] 可能为负数（当所有方向贡献为0，且 w[v] = -1 时），这是允许的

关键理解

为什么 f[v] 的定义是正确的？

对于节点 v，父节点方向能提供的最大贡献是：

1. 必须包含父节点 u（因为要连通到 v）
2. 可以选择 u 的其他孩子方向（如果它们的 dp_down 为正）
3. 可以选择 u 的父节点方向（如果 f[u] 为正）
4. 如果总和 ≤ 0，则 v 应该选择不连接父节点方向（取 max(0, ...)）

这样通过两次DFS，每个节点的答案就包含了所有可能的方向，确保了答案的正确性。