树型动态规划问题#

树型动态规划中最核心、也是最基础的操作，是 子树合并 。在树结构中，每个节点的子树之间天然相互独立，只通过父节点发生关联。因此，许多看似复杂的树上问题，都可以被分解为：先分别求出各个子树的最优解，再由父节点进行合并 。这一过程本质上是一种结构化的动态规划，自底向上地逐层汇总信息。

从这一视角出发，树型 DP 的状态往往定义在 “以某个节点为根的子树” 上，而转移则体现为 父节点如何整合来自子节点的贡献 。只要问题的约束不会在不同子树之间产生耦合关系，子树合并就可以作为基本框架反复使用。

基于子树合并，不同类型的问题会呈现出不同的转移形式：有的只需要对子节点状态进行简单求和或取最大值，有的需要在父节点处进行背包式的容量分配，还有的则可以借助 DFS 序，将这种合并过程进一步线性化。后文将从若干典型模型出发，逐步展开这些转移方式。

树上路径问题#

由于树是无环连通图，任意两个节点之间存在且仅存在一条简单路径。因此，在树上讨论路径时，不会出现折返或重复经过同一节点的情况，每个节点在一条简单路径中至多出现一次。这种结构特性使得路径问题具有良好的分解性质，可以通过对象贡献法进行分析。

所谓对象贡献法，即避开对 $O(n^2)$ 条路径的直接枚举，转而从局部元素（节点或边）的视角出发，计算其在所有合法路径中的参与度。与其统计每条路径包含哪些节点，不如统计每个节点被多少条路径覆盖。这种视角切换的核心在于：将 “路径对权值的累加” 转化为 “元素对路径的贡献” ，从而利用树上路径的唯一确定性，将复杂的全局统计解构为离散的局部计数问题。

以节点贡献为例，考虑删除某个节点 $u$ 后，整棵树会被分成若干个连通块，其规模分别为 $s_1, s_2, \dots, s_k$ 。设整棵树共有 $n$ 个节点。则所有经过节点 $u$ 的路径，可以理解为路径的两个端点分别位于不同的连通块（或其中一个端点就是 $u$ 本身）。通过对子树规模进行组合计数，可以计算出经过节点 $u$ 的路径条数，从而得到该点的贡献。

若问题涉及路径权值之和或路径长度统计，也可以采用类似思路。通常通过一次 DFS 预处理出每个子树的规模或其他辅助信息，再在回溯阶段计算每个节点或每条边在全局路径集合中的出现次数。这样便可将原本看似需要枚举 $O(n^2)$ 条路径的问题，转化为对每个节点或边进行一次局部计算，整体复杂度降为 $O(n)$ 。

从结构角度看，树上路径问题之所以适合使用贡献法，根本原因在于 路径的唯一性与无环性 。唯一性保证了路径与节点（或边）之间的对应关系是确定的，无环性保证了不会出现复杂的相互依赖关系。因此，全局路径统计问题可以分解为若干个局部贡献的求和问题。

二叉树直径长度#

题目链接

题目要点解析#

树上最大累加和#

题目链接

题目要点解析#

邻点决策问题#

在树结构中，图的边仅存在于父子节点之间，且整体无环。因此，若问题对相邻节点施加约束，则该约束仅作用于父子节点之间，不会在同层节点之间产生横向影响，也不会因环结构而形成复杂的连锁依赖。这种结构性特征保证了约束传播的局部性，使得问题可以通过树形动态规划进行有效分解。树的无环性是约束可分解性的前提 。

考虑一类典型模型：要求在树上选择若干节点，使得任意一条边的两个端点不能同时被选。设节点 $u$ 的权值为 $w_u$ ，其子节点集合为 $\{v_1, v_2, \ldots, v_m\}$ 。定义状态 $dp[u][0]$ 表示在以 $u$ 为根的子树中，且不选择节点 $u$ 时所能获得的最大权值；定义状态 $dp[u][1]$ 表示在以 $u$ 为根的子树中，且选择节点 $u$ 时所能获得的最大权值。

由于约束仅存在于父子之间，状态转移可直接由局部关系确定。全局最优性可以通过对子树最优性的组合得到，而不需要额外的全局协调 。当选择节点 $u$ 时，根据相邻点不可同时选的约束，其所有子节点均不能被选，因此有：

dp[u][1] = w_u + \sum_{i=1}^{m} dp[v_i][0]

当不选择节点 $u$ 时，对子节点不再施加限制，每个子节点可以独立地在 “选与不选” 两种状态中取最优，因此有：

dp[u][0] = \sum_{i=1}^{m} \max \Big( dp[v_i][0],\ dp[v_i][1] \Big)

上述转移仅依赖于子节点的状态，且不存在跨子树的耦合关系。不同子树之间相互独立，决策可以完全分解 。由此可通过一次自底向上的深度优先遍历完成全部状态计算，整体时间复杂度为 $O(n)$ 。从结构角度分析，该类问题之所以能够高效求解，根本原因在于树的无环性与层级结构保证了相邻约束的局部性。约束仅在父子节点之间传递，不会形成全局依赖闭环，从而使得整体最优解可以通过对子树最优解的组合得到。

没有上司的舞会#

题目链接

题目要点解析#

监控二叉树问题#

题目链接

题目要点解析#

相邻不同最长路#

题目链接

题目要点解析#

赫奇帕奇的金杯#

题目链接

题目要点解析#

换根转移问题#

在树型动态规划中，根节点是否固定、以及根的选择是否影响答案 ，本身就是题目性质的一部分。具体来看，树上 DP 的问题大致可以分为三类：一类是题目 明确规定了根节点 ，状态与转移均围绕该根展开；一类是题目 没有规定根节点，但无论选择哪个节点作为根，最终答案都相同 ；还有一类则是题目 既未规定根节点，且不同根对应的答案彼此不同 。换根 DP 正是为第三类问题服务的。

在这类问题中，我们往往需要求出 以每个节点作为根时的答案 。如果对每个节点都重新做一遍树形 DP，时间复杂度通常会膨胀到 $O(n^2)$ 。而换根 DP 的目标，是在 整体只进行线性规模计算 的前提下，高效地完成所有根的切换。从结构上看，换根并不会改变树的拓扑结构，只会改变 边的方向认知 ，也就是说原本的父子关系会发生翻转。对某个节点而言，当它成为新的根时，原来属于其父方向的部分，需要被视为一棵新的子树，并与原有的子树一起参与状态计算。因此，换根的本质并不是重新计算整棵树，而是一次 局部贡献的重新分配 。

典型做法通常分为两个阶段。第一阶段，任选一个节点作为初始根，自底向上进行一次 DFS，计算每个节点在 “只考虑其子树” 的条件下的 DP 值。第二阶段，再进行一次 DFS，将来自父节点方向的补充信息向下传递，使每个节点都能够在常数时间内构造出 “以自己为根” 时所需的完整状态。通过这种方式，每条边只会被正向、反向各处理一次，整体复杂度保持在 $O(n)$ 。

从更抽象的角度看，换根 DP 解决的是 状态定义依赖根节点的问题 。它要求我们将某个节点的整体状态，拆分为来自各个相邻方向的独立贡献，并保证这些贡献可以被删除、替换和重新组合。一旦这种可分解性成立，根节点的切换就不再需要重做计算，而只是一种视角上的平移。

最大深度和问题#

题目链接

题目要点解析#

染色的最大收益#

题目链接

题目要点解析#

翻转最少的首都#

题目链接

题目要点解析#

流量和最大的根#

题目链接

题目要点解析#

每个节点一定距离以内的权值和#

题目链接

题目要点解析#

可改重心的节点#

题目链接

题目要点解析#

用时最少的节点#

题目链接

题目要点解析#

树型依赖背包问题#

树型依赖背包是传统背包模型在拓扑结构上的进阶扩展。与普通背包中物品 “彼此独立、自由选取” 的逻辑不同，这类问题引入了明确的 依赖约束：若要选择某个特定物品，必须先选择其前置物品。这种制约关系排除了任意子集的可能性，要求选择方案必须在结构上构成一个 包含根节点的连通子图 。

从图论视角看，这种依赖关系通常抽象为一棵树或森林，其中父节点代表前置主件，子节点代表依赖附件。这使得问题的本质转化为：在树形结构的连通性约束下，寻优满足容量限制的最大价值子集 。这种结构特性决定了我们无法通过简单的线性扫描求解，而必须利用树的递归性质，通过树形动态规划将决策逻辑逐层向根节点汇聚。

在建模时，若依赖关系本身是一棵树，可以直接以根节点为起点进行树形动态规划；若依赖关系是多棵互不相连的树（即森林），则可以引入一个 虚拟根节点 ，将所有原本没有父节点的根节点连到该虚根上，并设虚根的体积和价值均为 $0$ 。这样，森林结构就被统一转化为一棵树，从而可以在同一套树形背包框架下处理。

设节点 $u$ 的子节点依次为 $\{v_1, v_2, \dots, v_m\}$ 。我们定义三维状态 $dp[u][i][j]$ 表示以节点 $u$ 为根的子树，已经处理完前 $i$ 个子节点（即 $v_1 \sim v_i$ ）且当前容量不超过 $j$ 所能获得的最大价值。

由于子节点的选择依赖于父节点，因此只有在选择了节点 $u$ 本身之后，才可以考虑其子节点。设节点 $u$ 的体积为 $v_u$ ，价值为 $w_u$ ，则当尚未处理任何子节点（即 $i=0$ ）时，有初始化：

dp[u][0][j] = \begin{cases} w_u & j \ge v_u \\ -\infty & j < v_u \end{cases}

随后依次合并子节点，当处理第 $i$ 个子节点 $v_i$ 时，需要在当前容量 $j$ 下为该子树分配一定容量 $k$ ，状态转移为：

dp[u][i][j] = \max_{0 \le k \le j} \Big( dp[u][i-1][j-k] + dp[v_i][m_i][k] \Big)

其中 $m_i$ 表示节点 $v_i$ 的子节点数， $dp[v_i][m_i][k]$ 表示子树 $v_i$ 在容量 $k$ 下的最优解。通过这种方式，子节点被逐一合并，相当于在节点 $u$ 上执行一次多阶段的分组背包。当所有子节点处理完毕（即 $i = m$ ）后， $dp[u][m][j]$ 即为以 $u$ 为根的整棵子树在容量 $j$ 下的最优值。如果存在虚根，最终答案即为 $dp[0][m_0][V]$ ，其中 $V$ 为背包总容量， $m_0$ 为虚根的子节点个数。

在时间复杂度方面，引入虚根 不会改变数量级 。设节点总数为 $n$ ，背包容量为 $V$ ，树形背包的主要开销来自对子节点逐一合并时的容量枚举。对于每条父子边，都会进行一次容量划分的转移，整体复杂度通常为 $O(nV^2)$ 。引入虚根后，节点数仅增加 $1$ ，边数增加若干条（等于原森林的树数），只是多进行一次合并操作，因此复杂度仍为 $O(nV^2)$ ，仅常数略有变化。

DFN序结构性优化#

树有一个非常重要的结构性质：在先序遍历中，每个节点的整棵子树一定对应一段连续区间。也就是说，如果我们在 DFS 过程中给每个节点一个编号 dfn[u] ，并记录该节点子树的大小 siz[u] ，那么节点 $u$ 的整棵子树在 DFN 序中恰好对应区间：

\Big[ dfn[u],\ dfn[u] + siz[u] - 1 \Big]

这意味着每个节点都可以在 $O(1)$ 的时间内确定自己子树在序列中的起止位置，原本分支状的树结构，被降维成一个线性数组。换句话说，树的层级包含关系被完整地编码进了区间的嵌套关系之中 。

这种 “子树区间连续性” 使得许多树上问题 可以自然地转化为区间问题 。例如，当我们需要快速查询某个节点子树的信息、对子树进行批量修改，甚至删除或统计整棵子树时，都可以先通过 DFS 编号将问题映射到区间上，再借助线段树、树状数组等线性数据结构进行维护。原本依赖递归遍历的操作，被替换为对一段连续区间的直接处理，结构更加规整，复杂度也更容易控制。

将树结构线性化之后，带依赖背包同样可以进行结构层面的重构。传统树形背包是在每个节点处逐个合并子节点，本质是多次分组背包的嵌套进行。而在 DFN 序下，整棵子树已经对应为一个连续区间，因此我们可以尝试直接在 DFN 序上进行线性动态规划。原本的层级合并，被转化为顺序决策问题 。

设整棵树按 DFS 序重新编号后，节点编号为 $1 \sim n$ 。由于 DFS 的访问顺序保证了一个节点的所有子节点一定出现在它之后，并且整棵子树一定是一个连续的区间，当我们处理到编号 $i$ 时，若选择该节点，就必须覆盖 整棵子树对应的区间 。同时，为保证转移所需的状态已经计算完成，我们需要对 $i$ 进行 倒序枚举 。

于是定义状态 $dp[i][j]$ 表示从 DFN 序位置 $i$ 开始考虑，在当前容量不超过 $j$ 的情况下所能获得的最大价值。接下来的关键在于状态转移的设计，当处理到节点 $u$ （其 DFN 编号为 $i$ ）时，有两种决策：不选该节点，则直接跳过整棵子树；选该节点，则消耗 $v_u$ 的容量，获得 $w_u$ 的价值，并继续考虑其子树内部的选择。

由于子树在 DFS 序中对应区间：

\Big[ dfn[u],\ dfn[u] + siz[u] - 1 \Big]

若不选节点 $u$ ，则必须直接跳转到：

i' = dfn[u] + siz[u]

因为其所有子节点在依赖约束下都无法被选择。于是转移可写为：

dp[i][j] = \max \Big( dp[i + siz[u]][j], \, \max_{j \geq v_u} \left( dp[i+1][j - v_u] + w_u \right) \Big)

第一项表示不选当前节点，直接跳过整棵子树；第二项表示选当前节点，然后继续在 DFN 序列中处理其子节点。可以看到，原本子树合并的过程，被替换为区间跳跃的过程。树的依赖关系不再通过嵌套循环进行维护，而是通过 DFN 序的区间结构保证合法性，一旦父节点未被选择，其整棵子树会被整体跳过，从而自动满足依赖约束 。

树型依赖背包 DFN 序优化的详细讲解可以看下面这个视频

这种写法的本质是将树形动态规划改写为带区间跳跃的线性动态规划，由于每个节点仅被处理一次，不再需要在每个父节点处反复枚举子节点进行合并，状态规模仅为 $O(nV)$ 。相比传统的 $O(nV^2)$ 合并式写法，这种结构更便于使用滚动数组进行空间压缩优化。从结构角度看，传统树形背包是自底向上逐层汇总的过程，而 DFN 优化后的写法则是沿 DFN 序的倒序扫描。

大学生最优选课#

题目链接