「USACO 2023.1 Platinum」Subtree Activation 题解

题目大意

给定一棵 $N$ 个节点的有根树，根为节点 $1$。每个节点初始未激活。每次操作可以翻转一个节点的状态（激活 ↔ 未激活）。要求找到一个最短的操作序列，使得：

1. 对于每棵子树，都存在某个时刻该子树恰好是所有激活节点的集合
2. 最终所有节点都未激活

解题思路

核心观察

这个问题可以转化为在树上寻找最优的遍历路径，使得能够访问所有子树状态。关键观察是：

• 每个节点需要被激活和失活各至少一次
• 子树之间的遍历顺序影响总操作次数
• 可以利用树形DP来优化遍历顺序

状态设计

代码中使用了三维DP状态：

• dp[u][0]：处理完以 $u$ 为根的子树，且 $u$ 处于未激活状态的最小操作次数
• dp[u][1]：处理完以 $u$ 为根的子树，且 $u$ 处于激活状态的最小操作次数
• dp[u][2]：处理完以 $u$ 为根的子树，且完成了所有子树访问的最小操作次数

状态转移

从叶子节点向上进行DP：

1. 初始化：对于叶子节点

   • dp[u][0] = 0（不需要操作）
   • dp[u][1] = 1（激活一次）
   • dp[u][2] = 2（激活+失活）

2. 合并子节点：

   // 关键转移方程
   dp[i][1] = min(dp[i][1], dp[i][0]);
   dp[i][2] = min(dp[i][2], dp[i][1]) + 2 * (++sz[i]);
   
   dp[p[i]][2] = min({dp[p[i]][2] + dp[i][2], 
                     dp[i][1] + dp[p[i]][1],
                     dp[p[i]][0] + dp[i][2] - 2 * sz[i]});
   dp[p[i]][1] = min(dp[p[i]][1] + dp[i][2], 
                    dp[i][1] + dp[p[i]][0]);
   dp[p[i]][0] += dp[i][2];
   

转移解释

• dp[i][1] = min(dp[i][1], dp[i][0])：从未激活到激活需要至少一次操作
• dp[i][2] = min(dp[i][2], dp[i][1]) + 2 * sz[i]：完成整个子树需要基础操作次数
• 三个状态的合并考虑了不同的遍历策略：
  • 直接合并子树
  • 链式合并优化
  • 利用已激活状态减少操作

算法流程

1. 输入处理：读取树结构
2. 自底向上DP：从叶子到根节点计算状态
3. 状态合并：对于每个节点，合并所有子节点的状态
4. 输出结果：根节点的 dp[1][2] 即为答案

复杂度分析

• 时间复杂度：$O(N)$，每个节点处理一次
• 空间复杂度：$O(N)$，存储DP状态和树结构

样例验证

对于样例：

3
1 1

树结构：

  1
 / \
2   3

计算过程：

• 节点2、3：dp[2][2] = dp[3][2] = 2
• 节点1：合并子节点状态，得到 dp[1][2] = 6

与题目给出的最优序列一致。

关键技巧

1. 状态压缩：用三个状态覆盖所有可能情况
2. 贪心合并：选择最优的子节点合并顺序
3. 操作计数：精确计算激活/失活操作次数

总结

这道题通过巧妙的树形DP状态设计，将复杂的操作序列优化问题转化为标准的状态转移问题。核心在于理解子树遍历的顺序优化和状态合并的策略选择。