树形DP-核心基础

树形动态规划（Tree DP）是动态规划在树结构上的应用，它结合了树的递归特性与DP的“分解子问题”思想，专门用于解决树结构中的最优解问题。从“树的最大独立集”到“二叉树的直径”，从“树上背包”到“树的中心”，树形DP都发挥着核心作用。

一、树形DP基础认知

1.1 树结构的特殊性

树是一种由n个节点和n-1条边组成的连通无环图，具有以下特性：

• 递归结构：任意节点的子树仍是树，适合递归处理。
• 唯一路径：任意两个节点之间有且仅有一条路径，避免了环带来的状态依赖问题。
• 根的可选性：树可以任意节点为根（通常选择0或1作为根），通过父节点与子节点的关系传递状态。

这些特性使得树形DP能够通过“自底向上”或“自顶向下”的递归方式，高效求解子树的最优解。

1.2 树形DP的核心思想

树形DP的核心是**“以子树的解推导父节点的解”**：

1. 定义状态：通常以“节点u”和“节点状态（如选/不选、颜色等）”为维度，记为dp[u][s]（s为状态参数），表示“以u为根的子树在状态s下的最优解”。
2. 递归分解：对于节点u，先递归求解其所有子节点v的dp[v][...]，再结合u与v的关系，计算u的dp[u][...]。
3. 遍历顺序：通常采用后序遍历（先处理子节点，再处理父节点），确保计算父节点时所有子节点的状态已确定。

1.3 与线性DP的区别

维度	线性DP（如0/1背包）	树形DP
数据结构	数组/序列	树（节点+边）
状态依赖	依赖前驱元素（i-1等）	依赖子节点（v）和父节点（u）
遍历方式	顺序遍历（从左到右）	后序遍历（自底向上）
核心难点	状态转移方程设计	树的递归处理与状态合并

二、树形DP的基本框架

2.1 步骤拆解

1. 建树：用邻接表存储树结构，标记父节点避免递归时重复访问（通常从根节点开始，递归时传入父节点参数）。
2. 定义状态：根据问题确定dp[u][s]的含义（如dp[u][0]表示“不选u时的最优解”，dp[u][1]表示“选u时的最优解”）。
3. 递归计算：
   • 初始化当前节点的状态（如叶子节点的基础值）。
   • 遍历所有子节点，递归计算子节点的dp值。
   • 根据子节点的dp值，更新当前节点的dp值（状态转移）。
4. 结果提取：根节点的dp值（或其状态组合）即为全局最优解。

2.2 通用代码模板

import java.util.*;public class TreeDPTemplate {List<List<Integer>> adj; // 邻接表存储树int[][] dp; // dp[u][s]：节点u在状态s下的最优解int n; // 节点数public TreeDPTemplate(int n) {this.n = n;adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}// 根据问题初始化dp数组（状态数由s的可能值决定）dp = new int[n][2]; // 示例：2种状态}// 添加无向边（建树时需区分父节点与子节点）public void addEdge(int u, int v) {adj.get(u).add(v);adj.get(v).add(u);}// 后序遍历：从根节点开始，parent为父节点private void dfs(int u, int parent) {// 1. 初始化当前节点的状态（根据问题定义）dp[u][0] = 0; // 示例：状态0的初始值dp[u][1] = 1; // 示例：状态1的初始值// 2. 遍历所有子节点（排除父节点）for (int v : adj.get(u)) {if (v == parent) continue; // 跳过父节点dfs(v, u); // 递归处理子节点// 3. 状态转移：结合子节点的dp值更新当前节点dp[u][0] += Math.max(dp[v][0], dp[v][1]); // 示例：状态0的转移dp[u][1] += dp[v][0]; // 示例：状态1的转移}}// 求解主函数（根节点通常设为0）public int solve() {dfs(0, -1); // 根节点的父节点设为-1（无效值）// 根据问题返回根节点的最优状态组合return Math.max(dp[0][0], dp[0][1]);}
}

三、经典案例详解

3.1 案例1：树的最大独立集

问题描述

最大独立集是指树上互不相邻的节点组成的集合，求该集合的最大节点数。

• 示例：

    1/ \
  2   3/ \4   5
  

  最大独立集为{2,4,5}或{1,4,5}，大小为3。

树形DP设计

1. 状态定义：

   • dp[u][0]：不选节点u时，以u为根的子树的最大独立集大小。
   • dp[u][1]：选节点u时，以u为根的子树的最大独立集大小。

2. 状态转移：

   • 若不选u：子节点v可选或不选，取最大值累加 → dp[u][0] += max(dp[v][0], dp[v][1])。
   • 若选u：子节点v必不能选，累加不选v的值 → dp[u][1] += dp[v][0]。

3. 边界条件：叶子节点u的dp[u][0] = 0，dp[u][1] = 1。

代码实现

import java.util.*;public class MaxIndependentSet {List<List<Integer>> adj;int[][] dp;int n;public MaxIndependentSet(int n) {this.n = n;adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}dp = new int[n][2];}public void addEdge(int u, int v) {adj.get(u).add(v);adj.get(v).add(u);}private void dfs(int u, int parent) {// 初始化：不选u为0，选u为1dp[u][0] = 0;dp[u][1] = 1;for (int v : adj.get(u)) {if (v == parent) continue;dfs(v, u);// 不选u：累加子节点的最大值dp[u][0] += Math.max(dp[v][0], dp[v][1]);// 选u：累加子节点不选的值dp[u][1] += dp[v][0];}}public int maxSetSize() {dfs(0, -1);return Math.max(dp[0][0], dp[0][1]);}public static void main(String[] args) {// 示例树：节点0(1), 1(2), 2(3), 3(4), 4(5)（对应示例中的1-5）MaxIndependentSet tree = new MaxIndependentSet(5);tree.addEdge(0, 1);tree.addEdge(0, 2);tree.addEdge(2, 3);tree.addEdge(2, 4);System.out.println(tree.maxSetSize()); // 输出3}
}

3.2 案例2：二叉树的直径

问题描述

二叉树的直径是指树上任意两个节点之间的最长路径长度（边数）。

• 示例：

      1/ \2   3/ \     
  4   5    
  

  直径为3（路径4-2-1-3或5-2-1-3，共3条边）。

树形DP设计

1. 状态定义：dp[u]表示以u为根的子树中，从u到任意叶子节点的最长路径长度（边数）。

2. 状态转移：

   • 对于叶子节点u：dp[u] = 0（无子节点，路径长度0）。
   • 对于非叶子节点u：若有左子树l和右子树r，则dp[u] = max(dp[l], dp[r]) + 1（取最长子树路径+1条边）。

3. 直径计算：在递归过程中，对于每个节点u，其左子树深度dp[l]与右子树深度dp[r]之和dp[l] + dp[r]可能是直径，需实时更新全局最大值。

代码实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }
}public class TreeDiameter {int maxDiameter = 0; // 全局最大直径public int diameterOfBinaryTree(TreeNode root) {dfs(root);return maxDiameter;}// 计算以u为根的子树的最大深度（边数），同时更新直径private int dfs(TreeNode u) {if (u == null) return -1; // 空节点深度为-1（叶子节点的子节点）int leftDepth = dfs(u.left); // 左子树深度int rightDepth = dfs(u.right); // 右子树深度// 当前节点的直径候选：左深度 + 右深度 + 2（左右各一条边）maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth + 2);// 返回当前子树的最大深度（边数）return Math.max(leftDepth, rightDepth) + 1;}public static void main(String[] args) {// 构建示例二叉树TreeNode root = new TreeNode(1);root.left = new TreeNode(2);root.right = new TreeNode(3);root.left.left = new TreeNode(4);root.left.right = new TreeNode(5);TreeDiameter solver = new TreeDiameter();System.out.println(solver.diameterOfBinaryTree(root)); // 输出3}
}

3.3 案例3：树上节点染色问题

问题描述

给树的每个节点染色，可选颜色为1~k，要求相邻节点颜色不同，求染色方案总数。

• 示例：k=2，树为1-2（两个节点），方案数为2×1=2（1染1则2染2，1染2则2染1）。

树形DP设计

1. 状态定义：dp[u][c]表示“以u为根的子树中，节点u染颜色c时的染色方案数”。

2. 状态转移：

   • 对于根节点u染颜色c，其每个子节点v只能染与c不同的颜色d（d≠c），则：
     dp[u][c] = product( sum_{d≠c} dp[v][d] )（所有子节点的方案数乘积）。

3. 边界条件：叶子节点u染颜色c的方案数为1（无限制，仅自身）。

代码实现

import java.util.*;public class TreeColoring {List<List<Integer>> adj;long[][] dp;int n, k;final long MOD = 1000000007; // 取模避免溢出public TreeColoring(int n, int k) {this.n = n;this.k = k;adj = new ArrayList<>();for (int i = 0; i < n; i++) {adj.add(new ArrayList<>());}dp = new long[n][k + 1]; // 颜色1~k}public void addEdge(int u, int v) {adj.get(u).add(v);adj.get(v).add(u);}private void dfs(int u, int parent) {// 初始化：叶子节点染色方案数为1for (int c = 1; c <= k; c++) {dp[u][c] = 1;}for (int v : adj.get(u)) {if (v == parent) continue;dfs(v, u);// 计算子节点v的可用颜色总和（排除与u相同的颜色）for (int c = 1; c <= k; c++) {long sum = 0;for (int d = 1; d <= k; d++) {if (d != c) {sum = (sum + dp[v][d]) % MOD;}}// 当前节点u染c的方案数 × 子节点v的可用方案数dp[u][c] = (dp[u][c] * sum) % MOD;}}}public long totalSchemes() {dfs(0, -1);// 累加根节点所有颜色的方案数long total = 0;for (int c = 1; c <= k; c++) {total = (total + dp[0][c]) % MOD;}return total;}public static void main(String[] args) {TreeColoring tree = new TreeColoring(2, 2); // 2个节点，2种颜色tree.addEdge(0, 1);System.out.println(tree.totalSchemes()); // 输出2}
}

四、树形DP的关键技巧

4.1 状态设计原则

• 明确状态维度：通常包含“节点u”和“状态参数s”（如选/不选、颜色、深度等），s的维度应尽可能小（避免复杂度爆炸）。
• 子树无关性：dp[u][s]应仅依赖子节点的状态，与父节点的其他子树无关（确保无后效性）。

4.2 树的遍历与父节点处理

• 避免重复访问：递归时必须传入parent参数，跳过父节点（树是无向图，邻接表中包含父节点）。
• 后序遍历优先：绝大多数树形DP需要先处理子节点，再合并结果到父节点，后序遍历是天然的适配方式。

4.3 复杂度分析

• 时间复杂度：设树有n个节点，状态数为s（如2种状态），则复杂度为O(n×s²)（每个节点需合并s种状态，每种状态需处理所有子节点）。
• 空间复杂度：O(n×s)（存储dp数组）+ O(n)（递归栈深度，最坏为链状树）。

总结

树形DP是解决树结构优化问题的核心方法，其核心在于利用树的递归特性，通过“自底向上”的后序遍历，将子树的最优解合并为父节点的解。从最大独立集的“选/不选”状态，到二叉树直径的“深度计算”，再到节点染色的“方案数乘积”，树形DP始终遵循“定义状态→递归求解子树→合并子树结果”的逻辑。

掌握树形DP的关键是：

1. 针对树的特点设计合适的状态（明确节点及其状态参数）；
2. 正确处理父节点与子节点的递归关系（避免重复访问）；
3. 在后序遍历中完成子树状态的合并与转移。

That’s all, thanks for reading~~
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～