树形动态规划中的换根实例操作

我们还是设当前 dfs 的点为 cur孩子节点是 nex。当前 cur 将变为下一个递归栈的孩子我们记录的 deep[] 将进行修改。以 3 号点转换到 4 号点为例转换关系如下图所示3 号点的子树此时少了一个少的子树是否影响新的高度呢上图的这个例子来看是影响的但下次转换到其他点时又不受影响了。可见这里又是一个二元状态影响 cur 高度不影响 cur 高度当 cur 受到 nex第一高的子树影响时此时 cur 的高度将被到第二高的子树决定。所以需要预先统计出最高子树值和次高子树值。这里用到一个小 tip单次遍历获取最大值和次大值pairint, int getFirstAndSecondMax(const vectorint 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}; }