树形DP

树形 DP 分为两部分。分别为树形操作和 DP（Dynamic Programming，动态规划）操作。
一般来说，对树形操作都会伴随广度或者深度优先搜索的操作。
而在这搜索中还伴随动态规划的状态转移，这就是树形 DP。

换根DP

换根 DP 是树形 DP 中的一个再度细分类型。
通常的场景是要求算出所有点作为根时，树的状态。如果是用普通的树形 DP 操作 $N$ 次，则时间复杂度通常会高达 $O(N^2)$ 。这个效率非常低。
而换根 DP 可以通过单次 dfs 的过程中，以 $O(1)$ 复杂度的消耗，算出孩子节点的状态。
因此换根 DP 也会被称为二次扫描的树形 DP。综合时间复杂度可以维护在 $O(N)$ 的数量级。

Input

解决问题

换根DP能解决不指定根结点，并且根节点的变化会对一些值产生影响的问题。例如子结点深度和、点权和等。如果要暴力求解出最优解，则我们可以枚举所有的节点为根，然后分别跑一次搜索，这样的时间复杂度会达到 $O(n^2)$，显然不可接受。这时可以考虑使用换根DP解决。

换根DP和树形DP不同

其相比于一般的树形DP具有以下特点：

以树上的不同点作为根，其解不同。
为其求解答案，不能单求某点的信息，需要求解每个节点的信息。
无法通过一次搜索完成答案的求解，因为一次搜索只能得到一个节点的答案。

解法

换根dp通常会与树形dp 结合，我们可以先任定一个根节点root，通过树形dp的思想计算出一个答案。但这样求解出的答案只是以root为根的解，并不能确定是不是最优解。于是再考虑当root的子节点作为根节点时，答案怎样变化。一般可以在 $O(1)$ 的时间复杂度内完成答案的转化。这样整道题的时间复杂度就由 $O(n^2)$ 降为了 $O(n)$。
总结一下,换根DP总共是三个步骤:

指定某个节点为根节点。
第一次搜索完成预处理（如子树大小等），同时得到以上述节点为根的解。
第二次搜索进行换根的动态规划，由已知解的节点推出相连节点的解。

Output

问题

给出一个 $n$ 个节点的树，求所有最小高度树的所有根节点。
以下列数据：$n=6, \text{edges}=[[3,0],[3,1],[3,2],[3,4],[5,4]]$。
分别以 $0 \sim 5$ 为根的树如图所示，深度分别为 $[3,3,3,2,2,4]$。

第一步：以任意一点统计

我们规定任意一个点作为根 root，进行树形 DP 的操作。
获取以确定 root 为根的状态下，所有子树的深度 deep[]。
具体的，设当前 dfs 的点为 cur，孩子节点是 nex：

对每个进入 dfs 的 deep[cur] 初始化为 1，表示当前节点可以有层数为 1 的贡献
遍历每个每个孩子节点

先递归操作 nex 节点，当递归结束到下一行代码时，表明 deep[nex] 已经计算好了
将获得的 deep[nex] 对当前 deep[cur] 进行松弛。注意松弛时，要累计上 cur 的这层，可得 deep[cur] = max(deep[cur], deep[nex] + 1)；

以上的描述，就是最基础的树形 DP 操作。也是换根 DP 中的第一轮扫描。
下方是假设以点 3 为 root 的搜索结果：

第二步：换根

我们还是设当前 dfs 的点为 cur，孩子节点是 nex。
当前 cur 将变为下一个递归栈的孩子，我们记录的 deep[] 将进行修改。
以 3 号点转换到 4 号点为例，转换关系如下图所示：

3 号点的子树此时少了一个，少的子树是否影响新的高度呢？上图的这个例子来看是影响的，但下次转换到其他点时又不受影响了。
可见这里又是一个二元状态：

影响 cur 高度
不影响 cur 高度

当 cur 受到 nex（第一高的子树）影响时，此时 cur 的高度将被到第二高的子树决定。所以需要预先统计出最高子树值和次高子树值。

这里用到一个小 tip，单次遍历获取最大值和次大值。

pair<int, int> getFirstAndSecondMax(const vector<int>& arr) {
    int first = 0, second = 0;
    for (int val : arr) {
        // 注意这里有等号
        if (val >= first) {
            second = first;
            first = val;
        } else if (val > second) {
            second = val;
        }
    }
    return {first, second};
}

步骤

我们可以获得代码的基本流程：

建图
第一次 dfs 获得 root 为根的整体状态
第二次 dfs 换根操作，每次 $O(1)$ 的统计出答案
回归题目，统计答案

Constraints

样题
MYOJ10403。
CF. Bear and Tree Jumps
最小高度树
STA-Station
USACO Gold, Great Cow Gathering
Tree
CF. Maximum White Subtree
CF. Choosing Capital for Treeland

10402: 学习系列 —— 换根DP

Description