「提高 - 71」二次扫描和换根法

二次扫描

在树形 DP 中，二次扫描指对树进行两遍 DFS。

第一次 DFS：自底向上

• 先处理儿子，再由儿子的信息计算父亲。

第二次 DFS：自顶向下

• 先计算父亲的信息，再传递给儿子。
• 将 子树外的信息补充进来。

第一遍 DFS 可以得知子树的信息，第二遍 DFS 用来告诉节点“上面和其他分支有什么”。

换根 DP

换根 DP，也叫 rerooting DP，解决的是：

一棵无根树，分别以每个节点作为根时，求出对应的答案。

因为以一个节点为根作一次树形 DP，时间复杂度通常为 $O(n)$。所以如果对每个节点都重新做一次树形 DP，复杂度变为 $O(n^2)$。

换根 DP 的一般步骤

1. 先任选一个元素为根，计算“子树方向”的信息；

   定义 down[x] 表示只考虑以 $x$ 为根的子树时，节点 $x$ 获得的贡献。第一次 dfs 可求出 down 数组。

2. 再把父节点除当前儿子方向以外的信息传给儿子，从而求出每个节点作为根时的答案。

   定义 up[x] 表示来自 (x) 子树之外，也就是父亲方向的贡献。

   父亲传给儿子的信息=父亲自己的上方信息 + 父亲自身贡献 + 其他儿子的贡献。

   在很多时候，求其他儿子的贡献会先求出所有儿子的贡献，在减去当前儿子的贡献。

3. 合并 up 和 down，找到最优解。