树形动态规划是一种在树形数据结构上应用动态规划思想的算法，它通过递归遍历树结构并利用子问题的解来构建整体问题的解。
一、基本概念与特点
树形DP具有以下特征：
- 层次性：树结构天然具有层次关系，适合自底向上或自顶向下的递推
- 递归性：树的子结构性质使得问题可以分解为子问题
- 无后效性：父节点的状态仅依赖于子节点的状态
二、核心思想与实现方式
1. 两种遍历方向
- 叶→根（后序遍历）：先处理子节点再更新父节点
void dfs(int u, int parent) {
for(int v : tree[u]) {
if(v != parent) {
dfs(v, u); // 先递归处理子节点
// 用子节点信息更新u的状态
}
}
}
- 根→叶（先序遍历）：预处理后再向下传递信息
void dfs(int u, int parent) {
// 预处理u的状态
for(int v : tree[u]) {
if(v != parent) {
// 传递信息给子节点
dfs(v, u);
}
}
}
3. 时间复杂度
一般为O(n)，n为节点数
三、经典问题与C++实现
1. 没有上司的舞会（最大独立集）
问题：选择节点集合，使得没有两个相邻节点被选中，且价值和最大
状态定义：
dp[u][0]：不选u时的最大值dp[u][1]：选u时的最大值
C++实现：
vector<vector<int>> tree;
vector<int> value;
vector<vector<int>> dp;
void dfs(int u, int parent) {
dp[u][1] = value[u]; // 选择u的初始值
for(int v : tree[u]) {
if(v == parent) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]); // u不选，子节点可选可不选
dp[u][1] += dp[v][0]; // u选了，子节点不能选
}
}
int maxIndependentSet(int root) {
dp.assign(n+1, vector<int>(2, 0));
dfs(root, -1);
return max(dp[root][0], dp[root][1]);
}
2. 树的最长路径（直径）
问题：求树上任意两点间的最长路径
解法：对于每个节点，记录：
d1[u]：u向下的最长路径d2[u]：u向下的次长路径
C++实现：
vector<vector<pair<int,int>>> tree; // 邻接表存储树
vector<int> d1, d2; // 最长和次长路径
int diameter = 0;
void dfs(int u, int parent) {
for(auto [v, w] : tree[u]) {
if(v == parent) continue;
dfs(v, u);
int len = d1[v] + w;
if(len > d1[u]) {
d2[u] = d1[u];
d1[u] = len;
} else if(len > d2[u]) {
d2[u] = len;
}
}
diameter = max(diameter, d1[u] + d2[u]);
}
3. 树上背包（选课问题）
问题：依赖前导课程的选课问题，求选m门课的最大价值
C++实现：
vector<vector<int>> tree;
vector<vector<int>> dp; // dp[u][j]: 以u为根选j门课的最大值
vector<int> credit;
int m;
void dfs(int u) {
for(int v : tree[u]) {
dfs(v);
// 逆向更新防止重复计算
for(int j = m; j >= 1; j--) {
for(int k = 1; k <= j; k++) {
dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);
}
}
}
}
四、应用场景与变种
- 实际应用：
• 组织结构优化（如员工排班）
• 网络路由优化
• 资源分配问题 - 常见变种问题：
• 树的重心
• 树的点覆盖
• 树的边覆盖
• 树的匹配问题
五、解题技巧
- 状态设计要点：
• 通常以dp[u][k]表示以u为根的子树在状态k下的最优解
• 考虑父子节点间的约束关系 - 实现技巧：
• 使用邻接表或链式前向星存储树
• 注意避免重复计算（记忆化）
• 处理森林时添加虚拟根节点
