什么是换根DP及第一步操作说明

第一步 以任意一点统计

我们规定任意一个点作为根 root，进行树形 DP 的操作。

获取以确定 root 为根的状态下，所有子树的深度 deep[]。

具体的，设当前 dfs 的点为 cur，孩子节点是 nex：

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

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

以上的描述，就是最基础的树形 DP 操作。也是换根 DP 中的第一轮扫描。

下方是假设以点 3 为 root 的搜索结果：