浅谈：树形动态规划中的换根技巧

什么是换根DP如大家所熟悉的‌换根DPRe-rooting DP是树形动态规划的一种优化技巧用于在一次预处理后高效计算以树中每个节点为根时的某种全局答案避免对每个根单独做一次 O(n) 树形 DP否则总复杂度 O(n²)‌核心思想‌先任选一节点如 1为根‌第一次 DFS自底向上‌ 计算其子树相关状态如子树大小、子树内距离和等再‌第二次 DFS自顶向下‌ 利用“换根公式”从父节点状态推导出子节点作为新根时的答案。树形 DP树形 DP 分为两部分。分别为树形操作和DPDynamic Programming动态规划操作。一般来说对树形操作都会伴随广度或者深度优先搜索的操作。而在这搜索中还伴随动态规划的状态转移这就是树形 DP。换根 DP换根 DP 是树形 DP 中的一个再度细分类型。通常的场景是要求算出所有点作为根时树的状态。如果是用普通的树形 DP 操作 n 次则时间复杂度通常会高达 。这个效率非常低。而换根 DP 可以通过单次 dfs 的过程中以 复杂度的消耗算出孩子节点的状态。因此换根 DP 也会被称为二次扫描的树形 DP。综合时间复杂度可以维护在 的数量级。