[Note] 树图DP

[L4] 树形/图形状态 动态规划

顾名思义，是以树或图为模型进行的动态规划。由于树和图本身具有明确的结构关系，DP 的状态转移往往紧扣其拓扑性质。

一、核心特征

1. 树形 DP

• 天然子结构：树的父子关系构成了天然的层级。通常通过 DFS（后序遍历） 实现，先递归处理子节点，再利用子节点的 DP 值回溯推导父节点。

• 状态转移：状态通常包含 $f[u][\dots]$，表示以 $u$ 为根的子树内的某种最优解。

• 子树合并：只有当不同孩子竞争同一种可加资源时，才需要枚举资源分配；具体循环方向和上界由状态语义决定，详见 树上背包模型。

2. 图形 DP

• 拓扑序：图上的 DP 必须在 DAG 上进行，或者通过 SCC 缩点 转化为 DAG，以保证转移的无环性。

• 层级划分：某些图 DP 通过 “层” 的概念（如时间步 $t$、倍增步 $2^k$）将图转化为线性/分层结构。

二、模型分类

树形DP

换根DP

树形 DP 中的换根 DP 问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会对一些值，例如子结点深度和、点权和等产生影响。

• 相关例题：

  • P2986 Great Cow Gathering G：换根DP，树上重心。

树上背包

树上背包不是带了第二维的树形 DP，而是把同一种可加资源分配给不同孩子的过程。标准入口、资源变形、接口状态与结构变换已由 树上背包模型 接管；P1352 这类只有少量父子选择状态的题仍属于普通树形 DP。

图形DP

DAG 上的 DP

在拓扑序基础上结合概率、期望或路径计数。

• 相关例题：

  • P4316 绿豆蛙的归宿：DAG 上的期望 DP，反向建图。

  • P2656 采蘑菇：强连通分量 (SCC) 缩点 + DAG 最长路。

  • P7077 函数调用：利用拓扑序反向计算执行权重的贡献统计。

路径上的 DP

此类模型中，状态和路径有关，例如说两点之间可达性 / 最短路，从 $u$ 走 $k$ 步到 $v$ 的方案数。

由于路径的分层不是特别明显，一般以路径长度或者点的顺序，或者题目的特殊条件来构造 DP 状态。

• 相关例题：

  • [[200_Publish/260_Records/DP/P1613 跑路]]：利用倍增思想 ($2^k$) 重新建图，再跑最短路。

  • P6772 美食家：图上的状态转移 / 矩阵加速优化。

  • P3953 逛公园：最短路 + $k$ 维度扩展，记忆化搜 + 计数DP。