树形 DP

树没有环，任选根后，子树之间相互独立。树形 DP 通常在一次后序 DFS 中聚合子节点状态。

最大独立集：没有上司的舞会

令 dp[u][0/1] 表示 u 不选/选时，u 的子树可获得的最大权值。若选 u，则孩子均不能选；若不选 u，每个孩子自由取两种状态最大值。

void dfs(int u,int fa){
  dp[u][1]=a[u];
  for(int v:g[u]) if(v!=fa){
    dfs(v,u);
    dp[u][0]+=max(dp[v][0],dp[v][1]);
    dp[u][1]+=dp[v][0];
  }
}

换根 DP

当每个点都要作为根求答案时，先自底向上求子树贡献，再自顶向下把父侧贡献传给儿子。常用两次 DFS：第一遍求 down[u]，第二遍利用前缀/后缀最大值或“最大、次大值”计算 up[v]，避免对每个儿子重复遍历兄弟。

复杂度

固定根的树 DP 每条边访问常数次，时间 O(n)、空间 O(n)。递归深度可能为 n，链状树须注意栈深；无向树 DFS 必须跳过父节点。

整理自 XOJ《树形DP》。