78.【必备】树型dp-下

本文的网课内容学习自B站左程云老师的算法详解课程，旨在对其中的知识进行整理和分享~

网课链接：算法讲解079【必备】树型dp-下_哔哩哔哩_bilibili

一.到达首都的最少油耗

题目：到达首都的最少油耗

算法原理

• 问题描述

  • 给定一棵树（无向无环图）和每个节点对应的字符，寻找最长的路径，要求路径上任意相邻节点的字符都不相同。

• 整体原理

  • 采用后序遍历递归处理，自底向上计算每个子树的最长有效路径，通过维护两个关键值来寻找全局最优解。

• 具体步骤

  • 构建树结构：

    • 使用邻接表存储树形结构
    • 根据parent数组建立父子关系

  • 定义信息类：

    • maxPathFromHead：必须从当前节点出发的最长有效路径
    • maxPath：当前子树中的最长有效路径（可能不包含当前节点）

  • 递归处理每个子树：

    • 叶子节点直接返回(1,1)
    • 非叶子节点： a) 收集所有子节点信息 b) 维护最长(max1)和次长(max2)有效子路径 c) 确保相邻节点字符不同

  • 计算当前节点信息：

    • maxPathFromHead = max1 + 1
    • maxPath = max(子树maxPath, max1 + max2 + 1)

  • 最终结果：

    • 根节点的maxPath即为全局解

  • 关键点解释

    • 双值维护：

      • maxPathFromHead用于向上传递
      • maxPath记录全局最优

    • 字符比较：

      • 只在相邻字符不同时考虑子路径

    • 路径组合：

      • 通过max1和max2计算可能的最长路径

• 复杂度分析

  • 时间复杂度：O(n)，每个节点处理一次
  • 空间复杂度：O(n)，存储树结构和递归栈

• 示例

  • 输入：parent = [-1,0,0,1,1,2] s = "aabccb"
  • 树结构：
    • a(0)
    • / \
    • a(1) b(2)
    • / \ \
    • c(3) c(4) b(5)
  • 处理过程：
    • 节点3/4/5：返回(1,1)
    • 节点1：
      • max1=1（节点3），max2=1（节点4）
      • 返回(2,3)（路径3-1-4）
    • 节点2：
      • max1=1（节点5）
      • 返回(2,2)
    • 根节点0：
      • max1=2（节点1），max2=2（节点2）
      • 最长路径=5（如3-1-0-2-5）

• 总结

  • 树形DP的典型应用
  • 通过双值维护实现高效计算
  • 严格遵循相邻字符不同的约束
  • 适用于树形结构的最长路径问题

代码实现

import java.util.ArrayList; // 相邻字符不同的最长路径 // 给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 // 这棵树由编号从 0 到 n - 1 的 n 个节点组成 // 用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树 // 其中 parent[i] 是节点 i 的父节点 // 由于节点 0 是根节点，所以 parent[0] == -1 // 另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符 // 请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 // 并返回该路径的长度 // 测试链接 : https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/ public class Code02_LongestPathWithDifferentAdjacent { public static int longestPath(int[] parent, String str) { int n = parent.length; char[] s = str.toCharArray(); ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int i = 1; i < n; i++) { graph.get(parent[i]).add(i); } return f(s, graph, 0).maxPath; } public static class Info { public int maxPathFromHead; // 一定要从头节点出发的情况下，相邻字符不等的最长路径长度 public int maxPath; // 整棵树上，相邻字符不等的最长路径长度 public Info(int a, int b) { maxPathFromHead = a; maxPath = b; } } public static Info f(char[] s, ArrayList<ArrayList<Integer>> graph, int u) { if (graph.get(u).isEmpty()) { // u节点是叶 return new Info(1, 1); } int max1 = 0; // 下方最长链 int max2 = 0; // 下方次长链 int maxPath = 1; for (int v : graph.get(u)) { Info nextInfo = f(s, graph, v); maxPath = Math.max(maxPath, nextInfo.maxPath); if (s[u] != s[v]) { if (nextInfo.maxPathFromHead > max1) { max2 = max1; max1 = nextInfo.maxPathFromHead; } else if (nextInfo.maxPathFromHead > max2) { max2 = nextInfo.maxPathFromHead; } } } int maxPathFromHead = max1 + 1; maxPath = Math.max(maxPath, max1 + max2 + 1); return new Info(maxPathFromHead, maxPath); } }

二.相邻字符不同的最长路径

题目：相邻字符不同的最长路径

算法原理

• 问题描述

  • 给定一棵树结构（无向无环图）和每个节点对应的字符，要求找出树中最长的路径，该路径需满足任意相邻节点的字符都不相同。路径长度由路径上的节点数量决定。

• 整体原理

  • 采用深度优先搜索（DFS）的后序遍历方式，自底向上递归计算每个子树的信息。通过维护两个关键值来寻找全局最优解：
  • 从当前节点出发的最长有效路径（maxPathFromHead）
  • 当前子树内的最长有效路径（maxPath）

• 具体步骤

  • 树结构构建

    • 使用邻接表（ArrayList<ArrayList<Integer>>）存储树形结构
    • 根据parent数组建立父子关系（parent[i]表示节点i的父节点）

  • 递归定义信息类

    • class Info {
      • int maxPathFromHead; // 必须包含当前节点的最长有效路径
      • int maxPath; // 当前子树中的最长有效路径（可不含当前节点）
    • }

  • 递归处理每个节点

    • 基本情况：叶子节点直接返回(1,1)
    • 递归情况： a) 初始化max1（最长子路径）、max2（次长子路径）和maxPath b) 遍历所有子节点：
      • 更新全局maxPath
      • 若当前节点与子节点字符不同，更新max1和max2 c) 计算当前节点信息：
      • maxPathFromHead = max1 + 1
      • maxPath = max(子树maxPath, max1 + max2 + 1)

  • 结果获取

    • 从根节点开始递归
    • 最终结果为根节点的maxPath值

  • 关键点说明

    • 双值维护机制

      • maxPathFromHead：保证路径连续性，用于向上传递
      • maxPath：记录全局最优解，可能来自子树或当前路径组合

    • 字符差异检查

      • 只在当前节点与子节点字符不同时考虑子路径
      • 确保路径中相邻节点字符不同

    • 路径组合逻辑

      • 最长路径可能由两条最长子路径通过当前节点连接而成（max1 + max2 + 1）
      • 同时考虑不经过当前节点的子树路径

• 复杂度分析

  • 时间复杂度：O(n)，每个节点仅处理一次
  • 空间复杂度：O(n)，用于存储树结构和递归栈

• 示例

  • 输入：parent = [-1,0,0,1,1,2] s = "aabccb"
  • 树结构：
    • a(0)
    • / \
    • a(1) b(2)
    • / \ \
    • c(3) c(4) b(5)
  • 处理过程：
    • 节点3/4/5（叶子节点）：
      • 返回(1,1)
    • 节点1：
      • max1=1（节点3或4），max2=1
      • maxPathFromHead=2（a→c）
      • maxPath=3（c→a→c）
      • 返回(2,3)
    • 节点2：
      • max1=1（节点5）
      • maxPathFromHead=2（b→b不合法，实际为1？需要修正）
      • 返回(1,1)（注：此处示例处理可能有误，实际b(2)与b(5)字符相同应跳过）
    • 根节点0：
      • max1=2（节点1），max2=0
      • maxPathFromHead=3（a→a→c不合法，实际应为a→b=2）
      • maxPath=max(3,2+0+1)=3
      • 最终最长路径：3（如c→a→b）
    • （注：示例中字符相同的情况需要特殊处理，实际代码已正确处理）

• 总结

  • 适用场景：树形结构中的条件约束路径问题
  • 算法优势：
    • 通过一次遍历完成计算
    • 严格保证相邻节点字符不同的约束
    • 高效找到全局最优解
  • 扩展性：可应用于其他树形路径约束问题
  • 该算法通过巧妙的双值维护和路径组合逻辑，高效解决了树形结构中带字符约束的最长路径问题。其核心在于后序遍历的信息传递和全局最优解的动态维护。

代码实现

import java.util.ArrayList; // 相邻字符不同的最长路径 // 给你一棵 树（即一个连通、无向、无环图），根节点是节点 0 // 这棵树由编号从 0 到 n - 1 的 n 个节点组成 // 用下标从 0 开始、长度为 n 的数组 parent 来表示这棵树 // 其中 parent[i] 是节点 i 的父节点 // 由于节点 0 是根节点，所以 parent[0] == -1 // 另给你一个字符串 s ，长度也是 n ，其中 s[i] 表示分配给节点 i 的字符 // 请你找出路径上任意一对相邻节点都没有分配到相同字符的 最长路径 // 并返回该路径的长度 // 测试链接 : https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/ public class Code02_LongestPathWithDifferentAdjacent { public static int longestPath(int[] parent, String str) { int n = parent.length; char[] s = str.toCharArray(); ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int i = 1; i < n; i++) { graph.get(parent[i]).add(i); } return f(s, graph, 0).maxPath; } public static class Info { public int maxPathFromHead; // 一定要从头节点出发的情况下，相邻字符不等的最长路径长度 public int maxPath; // 整棵树上，相邻字符不等的最长路径长度 public Info(int a, int b) { maxPathFromHead = a; maxPath = b; } } public static Info f(char[] s, ArrayList<ArrayList<Integer>> graph, int u) { if (graph.get(u).isEmpty()) { // u节点是叶 return new Info(1, 1); } int max1 = 0; // 下方最长链 int max2 = 0; // 下方次长链 int maxPath = 1; for (int v : graph.get(u)) { Info nextInfo = f(s, graph, v); maxPath = Math.max(maxPath, nextInfo.maxPath); if (s[u] != s[v]) { if (nextInfo.maxPathFromHead > max1) { max2 = max1; max1 = nextInfo.maxPathFromHead; } else if (nextInfo.maxPathFromHead > max2) { max2 = nextInfo.maxPathFromHead; } } } int maxPathFromHead = max1 + 1; maxPath = Math.max(maxPath, max1 + max2 + 1); return new Info(maxPathFromHead, maxPath); } }

三.移除子树后的二叉树高度

题目：移除子树后的二叉树高度

算法原理

• 问题描述

  • 给定一棵二叉树和查询数组queries，对于每个查询queries[i]，需要临时移除以该值为根节点的子树后，计算剩余树的高度。所有查询相互独立，每次查询后树会恢复初始状态。

• 整体原理

  • DFS预处理：通过深度优先搜索记录每个节点的深度、子树大小和dfn序号
  • 前缀/后缀最大值数组：构建左右两侧的最大深度数组，用于快速查询
  • 查询处理：利用预处理信息快速计算移除任意子树后的树高

• 具体步骤

  • DFS预处理阶段：
    • 为每个节点分配dfn序号（深度优先编号）
    • 记录每个节点的深度（从根节点到该节点的边数）
    • 计算每个节点的子树大小（包括自身）
    • 递归公式：size[i] = 1 + size[left] + size[right]
  • 构建极值数组：
    • maxl[i]：表示dfn前i个节点的最大深度
    • maxr[i]：表示dfn后i个节点的最大深度
    • 填充方式：maxl[i] = max(maxl[i-1], deep[i]) maxr[i] = max(maxr[i+1], deep[i])
  • 查询处理阶段：
    • 对于查询节点q： a) 获取其dfn序号：pos = dfn[q]b) 左半部分最大深度：maxl[pos-1]c) 右半部分最大深度：maxr[pos + size[pos]]d) 剩余树高：max(leftMax, rightMax)

  • 关键点说明

    • dfn序号的妙用：

      • 将树结构线性化
      • 子树节点在dfn数组中连续存储

    • 极值数组的意义：

      • 实现O(1)时间复杂度的区间最大深度查询
      • 避免每次查询都重新遍历树结构

    • 独立查询处理：

      • 预处理阶段捕获树的完整结构信息
      • 查询阶段只需组合预计算的值

• 复杂度分析

  • 时间复杂度：

    • 预处理：O(n)（DFS遍历）
    • 查询处理：O(m)（m次O(1)查询）
    • 总计：O(n + m)

  • 空间复杂度：

    • O(n)（存储dfn、deep、size等数组）

• 示例

  • 假设二叉树：
    • 1(3)
    • / \
    • 2(1) 3(2)
    • / \
    • 4(0) 5(0)
    • （括号内为节点值）
  • 预处理结果：
    • dfn = [0,1,2,3,4,5] （索引为节点值）
    • deep = [0,1,2,1,2,2] （dfn序号的深度）
    • size = [5,3,1,1,1,1] （子树大小）
    • 查询queries=的处理：
      • 查询节点2的dfn=2
      • 左半部分maxl=1
      • 右半部分从dfn=2+3=5开始，maxr=0
      • 剩余树高=max(1,0)=1

• 总结

  • 适用场景：需要频繁查询子树移除后信息的树形问题
  • 算法优势：
    • 通过线性化预处理实现高效查询
    • 完美处理独立查询要求
    • 空间换时间的经典应用
  • 扩展性：可应用于其他子树统计类问题
  • 该算法通过巧妙的预处理和极值数组设计，将复杂的树形查询问题转化为高效的线性查询问题，展示了算法设计中空间与时间权衡的精妙运用。

代码实现

// 移除子树后的二叉树高度 // 给你一棵 二叉树 的根节点 root ，树中有 n 个节点 // 每个节点都可以被分配一个从 1 到 n 且互不相同的值 // 另给你一个长度为 m 的数组 queries // 你必须在树上执行 m 个 独立 的查询，其中第 i 个查询你需要执行以下操作： // 从树中 移除 以 queries[i] 的值作为根节点的子树 // 题目所用测试用例保证 queries[i] 不等于根节点的值 // 返回一个长度为 m 的数组 answer // 其中 answer[i] 是执行第 i 个查询后树的高度 // 注意： // 查询之间是独立的，所以在每个查询执行后，树会回到其初始状态 // 树的高度是从根到树中某个节点的 最长简单路径中的边数 // 测试链接 : https://leetcode.cn/problems/height-of-binary-tree-after-subtree-removal-queries/ public class Code03_HeightRemovalQueries { // 不要提交这个类 public static class TreeNode { public int val; public TreeNode left; public TreeNode right; } // 提交如下的方法 public static final int MAXN = 100010; // 下标为节点的值 public static int[] dfn = new int[MAXN]; // 下标为dfn序号 public static int[] deep = new int[MAXN]; // 下标为dfn序号 public static int[] size = new int[MAXN]; public static int[] maxl = new int[MAXN]; public static int[] maxr = new int[MAXN]; public static int dfnCnt; public static int[] treeQueries(TreeNode root, int[] queries) { dfnCnt = 0; f(root, 0); for (int i = 1; i <= dfnCnt; i++) { maxl[i] = Math.max(maxl[i - 1], deep[i]); } maxr[dfnCnt + 1] = 0; for (int i = dfnCnt; i >= 1; i--) { maxr[i] = Math.max(maxr[i + 1], deep[i]); } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; i++) { int leftMax = maxl[dfn[queries[i]] - 1]; int rightMax = maxr[dfn[queries[i]] + size[dfn[queries[i]]]]; ans[i] = Math.max(leftMax, rightMax); } return ans; } // 来到x节点，从头节点到x节点经过了k条边 public static void f(TreeNode x, int k) { int i = ++dfnCnt; dfn[x.val] = i; deep[i] = k; size[i] = 1; if (x.left != null) { f(x.left, k + 1); size[i] += size[dfn[x.left.val]]; } if (x.right != null) { f(x.right, k + 1); size[i] += size[dfn[x.right.val]]; } } }

四.从树中删除边的最小分数

题目：从树中删除边的最小分数

算法原理

• 问题描述

  • 给定一棵无向连通树，每个节点有一个整数值。要求删除两条不同的边将树分成三个连通组件，计算每个组件所有节点值的异或值，找出最大异或值与最小异或值的最小可能差值。

• 整体原理

  • DFS预处理：通过深度优先搜索为节点分配dfn序号，并计算每个子树的异或和
  • 边对枚举：枚举所有可能的边对组合
  • 快速计算：利用dfn序和子树：利用dfn序和子树信息快速确定三种分割情况
  • 分数计算：对每种分割计算三个组件的异或值并求极差

• 具体步骤

  • 树结构构建：

    • 使用邻接表存储树结构
    • 建立双向边连接

  • DFS预处理：

    • 为每个节点分配dfn序号（深度优先编号）
    • 计算每个子树的异或和（xor数组）
    • 记录每个子树的大小（size数组）
    • 递归公式：xor[i] = nums[u] ^ xor[child1] ^ xor[child2] ^ ... size[i] = 1 + size[child1] + size[child2] + ...

  • 边对枚举与处理：

    • 枚举所有边对组合（i,j）
    • 对每对边： a) 确定两条边对应的dfn区间 b) 判断三种分割情况：
      • 边j在边i的子树内
      • 边j在边i的子树外 c) 计算三个组件的异或值

  • 分数计算：

    • 对每种分割情况：
      • 计算三个异或值sum1, sum2, sum3
      • 求极差：max(sum1,sum2,sum3) - min(sum1,sum2,sum3)
    • 维护最小极差

  • 关键点说明

    • dfn序的应用：

      • 将树结构线性化
      • 通过dfn比较快速判断子树包含关系

    • 异或和性质：

      • 利用异或的自反性（A^A=0）
      • 子树异或和的高效计算

    • 分割情况判断：

      • 通过dfn和size确定子树范围
      • 区分边在子树内/外的不同处理

• 复杂度分析

  • 时间复杂度：

    • 预处理：O(n)（DFS遍历）
    • 边对枚举：O(m^2)（m=n-1为边数）
    • 总计：O(n + m^2)

  • 空间复杂度：

    • O(n)（存储dfn、xor、size等数组）

• 示例

  • 假设树结构：

    • 0(1) / \ 1(2) 2(3) / \ 3(4) 4(5)

    • （括号内为节点值）
  • 预处理结果：
    • dfn = [1,2,3,4,5] （索引为节点编号）
    • xor = [3,6,3,4,5] （dfn序号的异或和）
    • size = [5,3,1,1,1] （子树大小）
  • 边对处理示例（边(0,1)和(1,3)）：
    • 边(0,1) dfn=2
    • 边(1,3) dfn=4
  • 判断：4在2的子树内（2 < 4 < 2+3）
  • 计算：
    • sum1 = xor = 5
    • sum2 = xor^xor = 6^5 = 3
    • sum3 = xor^xor = 3^6 = 5
  • 极差：max(5,3,5)-min(5,3,5)=2

• 总结

  • 适用场景：树形结构的分割优化问题
  • 算法优势：
    • 通过预处理实现高效查询
    • 巧妙利用dfn序处理子树关系
    • 异或性质简化计算
  • 扩展性：可应用于其他基于子树分割的问题
  • 该算法展示了如何通过树形结构的线性化预处理，将复杂的树操作问题转化为高效的数值计算问题，是树形数据结构处理的经典范例。

代码实现

import java.util.ArrayList; import java.util.Arrays; // 从树中删除边的最小分数 // 存在一棵无向连通树，树中有编号从0到n-1的n个节点，以及n-1条边 // 给你一个下标从0开始的整数数组nums长度为n，其中nums[i]表示第i个节点的值 // 另给你一个二维整数数组edges长度为n-1 // 其中 edges[i] = [ai, bi] 表示树中存在一条位于节点 ai 和 bi 之间的边 // 删除树中两条不同的边以形成三个连通组件，对于一种删除边方案，定义如下步骤以计算其分数： // 分别获取三个组件每个组件中所有节点值的异或值 // 最大 异或值和 最小 异或值的 差值 就是这种删除边方案的分数 // 返回可能的最小分数 // 测试链接 : https://leetcode.cn/problems/minimum-score-after-removals-on-a-tree/ public class Code04_MinimumScoreAfterRemovals { public static int MAXN = 1001; // 下标为原始节点编号 public static int[] dfn = new int[MAXN]; // 下标为dfn序号 public static int[] xor = new int[MAXN]; // 下标为dfn序号 public static int[] size = new int[MAXN]; public static int dfnCnt; public static int minimumScore(int[] nums, int[][] edges) { int n = nums.length; ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int[] edge : edges) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } Arrays.fill(dfn, 0, n, 0); dfnCnt = 0; f(nums, graph, 0); int m = edges.length; int ans = Integer.MAX_VALUE; for (int i = 0, a, b, pre, pos, sum1, sum2, sum3; i < m; i++) { a = Math.max(dfn[edges[i][0]], dfn[edges[i][1]]); for (int j = i + 1; j < m; j++) { b = Math.max(dfn[edges[j][0]], dfn[edges[j][1]]); if (a < b) { pre = a; pos = b; } else { pre = b; pos = a; } sum1 = xor[pos]; // xor[1] : 整棵树的异或和 // 因为头节点是0，一定拥有最小的dfn序号1 // f函数调用的时候，也是从0节点开始的 if (pos < pre + size[pre]) { sum2 = xor[pre] ^ xor[pos]; sum3 = xor[1] ^ xor[pre]; } else { sum2 = xor[pre]; sum3 = xor[1] ^ sum1 ^ sum2; } ans = Math.min(ans, Math.max(Math.max(sum1, sum2), sum3) - Math.min(Math.min(sum1, sum2), sum3)); } } return ans; } // 当前来到原始编号u，遍历u的整棵树 public static void f(int[] nums, ArrayList<ArrayList<Integer>> graph, int u) { int i = ++dfnCnt; dfn[u] = i; xor[i] = nums[u]; size[i] = 1; for (int v : graph.get(u)) { if (dfn[v] == 0) { f(nums, graph, v); xor[i] ^= xor[dfn[v]]; size[i] += size[dfn[v]]; } } } }

五.选课（普通解法，邻接表建图 + 相对好懂的动态规划）

题目：P2014 [CTSC1997] 选课

算法原理

• 问题描述

  • 给定N门课程，每门课程有学分和先修课要求（形成森林结构）。学生需要选择M门课程，要求若选择某课程则必须先修完其先修课程。求能获得的最大学分。

• 整体原理

  • 采用树形动态规划（DP）方法，将森林转换为以虚拟根节点连接的树，通过后序遍历递归计算各子树在不同选择数量下的最优解。

• 具体步骤

  • 建图处理：

    • 添加虚拟根节点0连接所有无先修课的课程
    • 使用邻接表存储树结构（graph）

  • 动态规划定义：

    • dp[i][j][k]：以i为根的子树，在前j个子树中选择k门课的最大学分
    • 初始化所有值为-1表示未计算

  • 递归函数设计：

    • 基本情况：
      • k=0时返回0（不选任何课）
      • j=0或k=1时只能选当前课程
    • 状态转移：
      • 不选第j棵子树：f(i,j-1,k)
      • 选第j棵子树的s门课：f(i,j-1,k-s) + f(v,child_size,s)
    • 记忆化存储计算结果

  • 结果计算：

    • 从虚拟根节点启动递归
    • 返回f(0, child_size, m)作为最终结果

  • 关键点说明

    • 虚拟根节点：

      • 将森林统一为树结构
      • 方便统一处理无先修课的课程

    • 三维DP设计：

      • 第一维：当前节点
      • 第二维：考虑的子节点范围
      • 第三维：剩余可选课程数

    • 转移方程：

      • 体现"选课必须选先修课"的约束
      • 通过子树组合计算最优解

• 复杂度分析

  • 时间复杂度：O(N*M²)
    • 每个节点处理M次
    • 每次处理最多M种分割方式
  • 空间复杂度：O(N*M)
    • 三维DP表存储中间结果

• 示例

  • 假设课程关系：
    • 虚拟0
    • ├─1(学分2)
    • ├─2(学分3)
    • │ └─3(学分1)
    • └─4(学分4)
  • 选择3门课的处理过程：
    • 节点3：只能选自己
    • 节点2：
      • 不选子树：选自己得3
      • 选子树：2+3=5（选2和3）
    • 最终在虚拟根计算最优组合

• 总结

  • 适用场景：树形依赖的选择优化问题
  • 算法优势：
    • 正确处理先修课约束
    • 记忆化避免重复计算
  • 教学价值：
    • 展示树形DP的经典应用
    • 演示森林转树的处理技巧
  • 该算法通过系统的状态设计和记忆化搜索，高效解决了课程选择这一经典树形依赖优化问题。

代码实现

// 选课 // 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习 // 在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习 // 现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课 // 若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b // 一个学生要从这些课程里选择 M 门课程学习 // 问他能获得的最大学分是多少 // 测试链接 : https://www.luogu.com.cn/problem/P2014 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的code，提交时请把类名改成"Main"，可以直接通过 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.ArrayList; // 普通解法，邻接表建图 + 相对好懂的动态规划 // 几乎所有题解都是普通解法的思路，只不过优化了常数时间、做了空间压缩 // 但时间复杂度依然是O(n * 每个节点的孩子平均数量 * m的平方) public class Code05_CourseSelection1 { public static int MAXN = 301; public static int[] nums = new int[MAXN]; public static ArrayList<ArrayList<Integer>> graph; static { graph = new ArrayList<>(); for (int i = 0; i < MAXN; i++) { graph.add(new ArrayList<>()); } } public static int[][][] dp = new int[MAXN][][]; public static int n, m; public static void build(int n) { for (int i = 0; i <= n; i++) { graph.get(i).clear(); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in = new StreamTokenizer(br); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while (in.nextToken() != StreamTokenizer.TT_EOF) { // 节点编号从0~n n = (int) in.nval; in.nextToken(); m = (int) in.nval + 1; build(n); for (int i = 1, pre; i <= n; i++) { in.nextToken(); pre = (int) in.nval; graph.get(pre).add(i); in.nextToken(); nums[i] = (int) in.nval; } out.println(compute()); } out.flush(); out.close(); br.close(); } public static int compute() { for (int i = 0; i <= n; i++) { dp[i] = new int[graph.get(i).size() + 1][m + 1]; } for (int i = 0; i <= n; i++) { for (int j = 0; j < dp[i].length; j++) { for (int k = 0; k <= m; k++) { dp[i][j][k] = -1; } } } return f(0, graph.get(0).size(), m); } // 当前来到i号节点为头的子树 // 只在i号节点、及其i号节点下方的前j棵子树上挑选节点 // 一共挑选k个节点，并且保证挑选的节点连成一片 // 返回最大的累加和 public static int f(int i, int j, int k) { if (k == 0) { return 0; } if (j == 0 || k == 1) { return nums[i]; } if (dp[i][j][k] != -1) { return dp[i][j][k]; } int ans = f(i, j - 1, k); // 第j棵子树头节点v int v = graph.get(i).get(j - 1); for (int s = 1; s < k; s++) { ans = Math.max(ans, f(i, j - 1, k - s) + f(v, graph.get(v).size(), s)); } dp[i][j][k] = ans; return ans; } }

六.选课（最优解，链式前向星建图 + dfn序的利用 + 巧妙定义下的尝试）

题目：P2014 [CTSC1997] 选课

算法原理

• 问题描述

  • 给定N门课程及其先修关系（形成森林结构），每门课程有对应学分。要求选择M门课程，且选择某课程必须先修完其先修课程。求能获得的最大学分。

• 整体原理

  • 采用链式前向星建图+DFN序处理+动态规划的最优解法，通过树形线性化和逆向DP计算，将时间复杂度优化至O(N*M)。

• 具体步骤

  • 树形结构预处理：

    • 使用链式前向星存储树结构
    • 添加虚拟根节点0连接所有无先修课的课程
    • 进行DFS遍历，为每个节点分配DFN序号
    • 记录每个节点的子树大小(size)和学分(val)

  • 动态规划定义：

    • dp[i][j]：从DFN序i到n+1的节点中选择j个形成有效结构的最大学分
    • 有效结构定义：选择的节点在树形结构上是连续的

  • 逆向DP计算：

    • 按DFN序从大到小处理
    • 状态转移方程：
      • 不选当前节点：dp[i][j] = dp[i+size[i]][j]
      • 选当前节点：dp[i][j] = val[i] + dp[i+1][j-1]
    • 取两种选择的最大值

  • 结果计算：

    • 最终结果为虚拟根节点学分加上dp[m]
    • 保证整体选择的课程数恰好为M门

  • 关键创新点

    • DFN序的巧妙应用：

      • 将树形结构转化为线性序列
      • 通过DFN序保证子树节点连续存储

    • 逆向DP设计：

      • 从叶子节点向根节点计算
      • 利用size数组快速跳过子树范围

    • 有效结构定义：

      • 确保选择的课程集合在树形结构上连通
      • 自然满足先修课程约束条件

• 复杂度分析

  • 时间复杂度：O(N*M)
    • DFS预处理：O(N)
    • DP计算：O(N*M)
  • 空间复杂度：O(N*M)
    • 存储DP表

• 示例

  • 假设课程关系：
    • 虚拟0(学分0)
    • ├─1(2)
    • ├─2(3)
    • │ └─3(1)
    • └─4(4)
  • DFN序分配：1:0, 2:1, 3:2, 4:3, 5:4
  • DP计算过程（m=3）：
    • 处理节点5：只能选自己
    • 处理节点4：选4得4分
    • 处理节点3：选3得1分
    • 处理节点2：
      • 不选：继承节点4的结果
      • 选：3 + 节点3的结果
    • 最终组合：选2、3、4得8分

• 总结

  • 效率提升：

    • 相比传统树形DP的O(NM²)优化到O(NM)
    • 避免重复计算子树信息

  • 实现简洁：

    • 通过DFN序简化树形结构处理
    • 状态转移方程清晰明确

  • 扩展性强：

    • 可应用于其他树形依赖的选择问题
    • 方法可推广到更复杂的约束条件
  • 该算法通过创新的线性化处理和逆向动态规划，完美解决了课程选择这一经典问题，展示了算法设计中对问题本质的深刻理解和巧妙转化。

代码实现

// 选课 // 在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习 // 在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习 // 现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课 // 若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b // 一个学生要从这些课程里选择 M 门课程学习 // 问他能获得的最大学分是多少 // 测试链接 : https://www.luogu.com.cn/problem/P2014 // 请同学们务必参考如下代码中关于输入、输出的处理 // 这是输入输出处理效率很高的写法 // 提交以下的code，提交时请把类名改成"Main"，可以直接通过 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; import java.util.Arrays; // 最优解，链式前向星建图 + dfn序的利用 + 巧妙定义下的尝试 // 时间复杂度O(n*m)，觉得难可以跳过，这个最优解是非常巧妙和精彩的！ public class Code05_CourseSelection2 { public static int MAXN = 301; public static int[] nums = new int[MAXN]; // 链式前向星建图 public static int edgeCnt; public static int[] head = new int[MAXN]; public static int[] next = new int[MAXN]; public static int[] to = new int[MAXN]; // dfn的计数 public static int dfnCnt; // 下标为dfn序号 public static int[] val = new int[MAXN + 1]; // 下标为dfn序号 public static int[] size = new int[MAXN + 1]; // 动态规划表 public static int[][] dp = new int[MAXN + 2][MAXN]; public static int n, m; public static void build(int n, int m) { edgeCnt = 1; dfnCnt = 0; Arrays.fill(head, 0, n + 1, 0); Arrays.fill(dp[n + 2], 0, m + 1, 0); } public static void addEdge(int u, int v) { next[edgeCnt] = head[u]; to[edgeCnt] = v; head[u] = edgeCnt++; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in = new StreamTokenizer(br); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while (in.nextToken() != StreamTokenizer.TT_EOF) { n = (int) in.nval; in.nextToken(); m = (int) in.nval; build(n, m); for (int i = 1; i <= n; i++) { in.nextToken(); addEdge((int) in.nval, i); in.nextToken(); nums[i] = (int) in.nval; } out.println(compute()); } out.flush(); out.close(); br.close(); } public static int compute() { f(0); // 节点编号0 ~ n，dfn序号范围1 ~ n+1 // 接下来的逻辑其实就是01背包！不过经历了很多转化 // 整体的顺序是根据dfn序来进行的，从大的dfn序，遍历到小的dfn序 // dp[i][j] : i ~ n+1 范围的节点，选择j个节点一定要形成有效结构的情况下，最大的累加和 // 怎么定义有效结构？重点！重点！重点！ // 假设i ~ n+1范围上，目前所有头节点的上方，有一个总的头节点 // i ~ n+1范围所有节点，选出来j个节点的结构， // 挂在这个假想的总头节点之下，是一个连续的结构，没有断开的情况 // 那么就说，i ~ n+1范围所有节点，选出来j个节点的结构是一个有效结构 for (int i = n + 1; i >= 2; i--) { for (int j = 1; j <= m; j++) { dp[i][j] = Math.max(dp[i + size[i]][j], val[i] + dp[i + 1][j - 1]); } } // dp[2][m] : 2 ~ n范围上，选择m个节点一定要形成有效结构的情况下，最大的累加和 // 最后来到dfn序为1的节点，一定是原始的0号节点 // 原始0号节点下方一定挂着有效结构 // 并且和补充的0号节点一定能整体连在一起，没有任何跳跃连接 // 于是整个问题解决 return nums[0] + dp[2][m]; } // u这棵子树的节点数返回 public static int f(int u) { int i = ++dfnCnt; val[i] = nums[u]; size[i] = 1; for (int ei = head[u], v; ei > 0; ei = next[ei]) { v = to[ei]; size[i] += f(v); } return size[i]; } }