问题分析

我们有一个 $N$ 个节点的树结构，某些节点上装有发电机组。我们可以选择开启部分发电机组的开关，但需遵守以下约束条件：

在任意简单路径上，如果存在三个节点 $x \to y \to z$ 都被选择，那么中间节点 $y$ 的发电机组会损坏。

每个激活的发电机组（被选择且未损坏）带来 $1$ 日元收益，每个损坏的发电机组带来 $1$ 日元损失。目标是最大化利润（收益 - 损失）。

关键转化

约束条件等价于：被选择的节点集合中，任意连通块的大小不能超过 2。

换句话说：

• 可以选择孤立的单个节点
• 可以选择相邻的两个节点（形成一条边）
• 但不能选择三个或更多个连通的节点

树形DP状态设计

定义 $dp[u][state]$ 表示以节点 $u$ 为根的子树中，根据 $u$ 的选择状态所能获得的最大利润。

设计三种状态：

• 状态 0：节点 $u$ 不被选择
• 状态 1：节点 $u$ 被选择，且是孤立节点或路径端点
• 状态 2：节点 $u$ 被选择，且是某个长度为 2 的路径的中间节点

状态转移方程

情况1：节点 $u$ 有发电机组

1. $dp[u][0]$（$u$ 不选）：

   • 子节点可以任意选择
   • $dp[u][0] = \sum\limits_{v \in children(u)} \max(dp[v][0], dp[v][1], dp[v][2])$

2. $dp[u][1]$（$u$ 选，作为孤立节点）：

   • 获得 $1$ 日元收益
   • 所有子节点都不能被选择（避免形成连续三个）
   • $dp[u][1] = 1 + \sum\limits_{v \in children(u)} dp[v][0]$

3. $dp[u][2]$（$u$ 选，作为路径中间节点）：

   • 获得 $1$ 日元收益
   • 恰好有一个子节点被选择（状态 1 或 2），其他子节点都不选
   • 设 $diff[v] = \max(dp[v][1], dp[v][2]) - dp[v][0]$
   • $dp[u][2] = 1 + \sum dp[v][0] + \max\limits_{v} diff[v]$

情况2：节点 $u$ 没有发电机组

1. $dp[u][0]$（$u$ 不选）：

   • 基础值：$\sum \max(dp[v][0], dp[v][1], dp[v][2])$
   • 额外：可以选择至多 2 个子节点处于被选择状态
   • 设 $diff[v] = \max(dp[v][0], dp[v][1]) - dp[v][0]$，排序取前 2 大

2. $dp[u][1]$ 和 $dp[u][2]$：设为负无穷（不可能选择没有发电机组的节点）

算法流程

1. 输入处理：读取树结构和发电机组信息
2. DFS遍历：从根节点开始进行深度优先搜索
3. 状态计算：对于每个节点，根据是否有发电机组分别计算三种状态的值
4. 结果输出：根节点的最大状态值即为答案

复杂度分析

• 时间复杂度：$O(N \log N)$，主要来自对子节点差异值的排序
• 空间复杂度：$O(N)$，存储树结构和DP状态

正确性证明

该DP设计的正确性基于以下观察：

1. 状态完备性：三种状态覆盖了所有可能的情况

   • 状态 0：当前节点不参与选择
   • 状态 1：当前节点作为路径端点或孤立节点
   • 状态 2：当前节点作为长度为 2 的路径的中间节点

2. 约束满足性：通过状态转移的限制，确保不会出现三个连续被选择的节点

   • 状态 1 要求所有子节点都不选
   • 状态 2 要求恰好一个子节点被选择
   • 对于无发电机组的节点，限制最多选择 2 个子节点

3. 最优子结构：每个子树的最优解可以由其子子树的最优解组合得到

总结

本题的核心在于将路径约束转化为对连通块大小的限制，并通过精巧的树形DP状态设计来实施这一限制。状态的定义体现了节点在可能路径中的角色，而转移方程则确保了约束条件的满足。