树形动态规划

本节目标

在后序汇总子树信息，并把根的答案传给子树。

决策附着在节点或边上，子树之间只通过父子关系连接。递归遍历基础见子树信息递归。

状态必须说明“当前节点是否选取、是否被覆盖”或“当前根外部信息是什么”。子节点状态合并后才得到父节点状态。

后序处理先得到子树答案；换根题先以根建立父序，再逆序汇总规模，最后正序下传答案。

dfs(node, parent):
  for child: dfs(child, node)
  merge child states into node state

每条边通常只访问常数次，因此时间 O(n)、辅助空间为递归栈或父序数组 O(n)。

把跨调用的答案存为未重置成员变量，或在换根时漏掉 n - 2 * size[child] 的双向变化。

树被拆成独立子树时使用本框架；图存在环时要额外处理访问和环，不能直接套树递归。