换根DP总结
作者:
SpongeBob_
,
2023-05-26 17:22:10
,
所有人可见
,
阅读 386
换根DP
树形 DP 中的换根 DP 问题又被称为二次扫描,通常不会指定根结点,并且根结点的变化会对一些值,例如子结点深度和、点权和等产生影响。
通常需要两次 DFS,第一次 DFS 预处理诸如深度,点权和、子树大小 [节点数量]、最长链和次长链之类的信息,在第二次 DFS 进行 DP 状态的转移。
两次 DFS 具体是自项向下还是自底向上维护信息取决于待维护的信息,不是固定的
经典例题:
1. 树的中心 —— 典中典
2. 计算机
3. 积蓄程度
4. 最小高度树
5. 树中距离之和
6. 统计可能的树根数目
7. 电
持续更新例题 ~