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

第一步 以任意一点统计我们规定任意一个点作为根 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 的搜索结果