树形DP和换根DP
树形DP
固定一个根节点。在树上做DP. 往往是树dfs遍历，先子树再基于子树结果对当前节点DP递推到根节点。
对于图转树的DFS遍历，其实就是无向树。
class DoubleTree:
def tree_dfs(graph, root):
'''
这种树上dfs不需要维护visit记录，只需要记录遍历刀当前节点的parent就可以了。时间复杂度o(n)
'''
import collections
p = collections.defaultdict(lambda: -1)
def dfs(u):
if len(graph[u]) == 1 and u in p:
print("is leaf")
for v in graph[u]:
if p[u] != v: # 非访问过
# 多次生效，针对多个v
p[v] = u
dfs(v)
def dfs_p(u, p):
if len(graph[u]) == 1 and u != root:
# 判断叶子节点时要用和这个双重判断
print("is leaf")
for v in graph[u]:
if v != p:
dfs_p(v, u)
也可以通过 g[0].append(-1) # 防止根节点被认作叶子
经典树形DP
124. 二叉树中的最大路径和 给你一个二叉树的根节点
root，返回其 最大路径和 。class Solution: ans = float('-inf') def maxPathSum(self, root: TreeNode) -> int: def dfs(node): if not node: return 0 l = dfs(node.left) r = dfs(node.right) self.ans = max(self.ans, max(l, 0) + max(r, 0) + node.val) return max(l, r, 0) + node.val dfs(root) return self.ans- 310. 最小高度树
- 6294. 最大价值和与最小价值和的差值 求最长直径，随便固定一个点为root。 树形DP
- 2246. 相邻字符不同的最长路径 和最大路径和一样
换根DP
换根DP就是再已知u节点为根节点的情况下，取u节点的一个孩子节点作为新的根节点，不断递归，求出所有节点为根节点情况时的结果。这其实就是一个二次dfs的过程。
第一次dfs是处理0节点为根节点的情况。
第二次dfs是0节点换根到其中子节点，并不断重复的dfs.
两次dfs都是在一个双向图上做遍历。因此要用dfs(u, p)这种dfs方式。
def dfs(u, p):
# dp[u] 根据子节点的预处理数组更新, optional
for v in graph[u]:
if v == p: continue
# xxxx
# 预处理数组更新, h0[u] = xxx, h0[v] = xxx, optional
# dp[u] 更新作为非根时变换, optional
# dp[v] 更新作为根时变换, optional
dfs(v, u) # 换根
# 恢复dp[u], dp[v], 预处理数组到u为根节点时的状态
第二次dfs时，u节点已经是根节点了，如果有预处理数组，则u的子节点的值已经转成正确的了，计算机u节点的dp值就可以根据u的子节点预处理数组计算了。
换根到子节点前，也需要更新下预处理数组中关于u节点的信息，因此换根后u节点就是子节点了。
记住每次改变只有u 和 v的dp值改变，以及预处理数组中关于u和v的值改变。
通常题目：
- 求满足条件的根的可能数量
- 求每个节点为根时的一个结果。
时间复杂度通常是O(n)
预处理数组
换根时预处理数组转换
- 孩子节点数目size。834. 树中距离之和
- 孩子最大高度。310. 最小高度树
- 孩子最长路径节点价值和。类似最大高度。2538. 最大价值和与最小价值和的差值
树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。
通常需要两次 DFS，第一次 DFS 预处理诸如深度，点权和之类的信息，在第二次 DFS 开始运行换根动态规划。
第二次dfs时，把父节点作为子树。来调整。比如 参考
需要计算出换根后的值的变化。 然后枚举根。
每次换根只能换相邻的。否则影响其它节点计算。只有相邻时只影响相邻的。而且枚举的一定是根，而不是第三个点为根的情况的相邻递推。
换根后不用恢复数据，因为是邻接点递推的。其它的没用。
记住每次改变只有u 和 v的dp值改变。详细
- 834. 树中距离之和 给定一个无向、连通的树。树中有
n个标记为0...n-1的节点以及n-1条边 。返回长度为n的数组answer，其中answer[i]是树中第i个节点与所有其他节点之间的距离之和。 - 310. 最小高度树 参考题解
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
graph = collections.defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
h0 = [0 for _ in range(n)]
def dfs(u, p):
nonlocal h0
l = 0
for v in graph[u]:
if v == p: continue
l = max(l, dfs(v, u) + 1)
h0[u] = l
return l
dfs(0, -1)
# print(h0)
dp = [0] * n
def dfs2(u, p):
nonlocal dp
# 此时就是u为root，每次进入函数都是已经换根为u了。此时孩子的h0是准的，h0[u]是不准的，需要根据孩子重新计算
first, second = -1, -1
for v in graph[u]:
if h0[v] >= first:
second = first
first = h0[v]
elif h0[v] >= second:
second = h0[v]
dp[u] = first + 1
# print(u, dp[u])
for v in graph[u]:
if v == p: continue
# 假设u与v换根
h0[u] = first if h0[v] != first else second
h0[u] += 1
dfs2(v, u)
dfs2(0, -1)
# print(dp)
minv = min(dp)
ans = []
for i in range(n):
if dp[i] == minv:
ans.append(i)
return ans
- 6294. 最大价值和与最小价值和的差值 换根DP
class Solution:
def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
graph = collections.defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
# 求最大价值和
h0 = [0 for _ in range(n)]
# 第一次遍历，统计以0为根的结果
def dfs(u, p):
nonlocal h0
l = price[u]
for v in graph[u]:
if v == p: continue
dfs(v, u)
l = max(l, price[u] + h0[v])
h0[u] = l
return l
dfs(0, -1)
# print(h0)
dp = [0] * n
def dfs2(u, p):
nonlocal dp
# 此时就是u为root，每次进入函数都是已经换根为u了。此时孩子的h0是准的，h0[u]是不准的，需要根据孩子重新计算下h0[u]
first, second = 0, 0
dp[u] = 0
for v in graph[u]:
# 此时不能continue，因为p是有用的，u为root,无p
# if v == p: continue
if h0[v] >= first:
second = first
first = h0[v]
elif h0[v] >= second:
second = h0[v]
# 以u为根情况下 h0和dp的值
dp[u] = first
h0[u] = first + price[u]
# print(u, dp[u], first, second)
for v in graph[u]:
if v == p: continue
# 假设u与v换根
h0[u] = price[u] + (first if (h0[v] != first) else second)
dfs2(v, u)
dfs2(0, -1)
return max(dp)