换根dp oiwiki
树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。
通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。
简单例题1
设f[i]是以i节点为根的所有节点深度之和，那么用树上dp的思路考虑如何做到状态转移。
假设以某种遍历顺序(如直接以1节点为根节点)，u是v的父节点，则：
所有在 v 的子树上的结点深度都减少了1，那么总深度和就减少了$ s_v；$
所有不在 v 的子树上的结点深度都增加了1，那么总深度和就增加了$ n-s_v；$
根据这两个条件就可以推出状态转移方程 $f_v = f_u - s_v + n - s_v=f_u + n - 2 \times s_v$。
综上可得：第一遍dfs处理出s，表示以i节点及其子树的节点数量。以及f[1]。
第二遍dfs运行动态规划求出所有f。
例题2 牛客小白赛E
实际上就是求经过i点的最长路径的板子题。
不需要管路径上经过了什么类型的点，直接求经过i点的最长路径，然后根据点i个类型更新k-路径的最大值即可。