苏三公子1. 树形DP基础概念解析
树形动态规划（Tree DP）是算法竞赛中处理树结构问题的核心方法。与线性DP不同，树形DP需要考虑节点间的父子关系和树的拓扑结构。典型场景包括：求树的最大独立集、最长路径、最小点覆盖等。其本质是通过后序遍历（或DFS）自底向上传递状态信息。
关键特征：每个节点的状态计算依赖于其子节点的状态，通常采用"子节点处理完毕后再处理父节点"的递归顺序。
树形DP的三大核心要素：
- 状态定义：
dp[u][s]表示以u为根的子树在状态s下的最优解 - 转移方程：父节点状态由子节点状态组合得到
- 边界条件：叶子节点的初始状态设定
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 经典问题模型与状态设计
2.1 最大独立集问题
定义：选择不相邻节点使权值和最大
状态设计：
dp[u][0]：不选u节点时的最大值dp[u][1]：选择u节点时的最大值
转移方程：
python复制dp[u][0] += max(dp[v][0], dp[v][1]) # v是u的子节点
dp[u][1] += dp[v][0] + weight[u]
2.2 最小点覆盖问题
定义：选择最少的点覆盖所有边
状态设计：
dp[u][0]：u不被选中时子树最小覆盖数dp[u][1]：u被选中时子树最小覆盖数
转移方程：
python复制dp[u][0] += dp[v][1] # 父不选则子必选
dp[u][1] += min(dp[v][0], dp[v][1])
2.3 树的最长路径问题
定义：求树上任意两点的最大距离
常用解法：
- 二次DFS法：任选一点找最远点，再从该点找最远点
- 树形DP法：
dp[u][0]：u向下的最长路径dp[u][1]：u向下的次长路径- 全局变量维护
max_len = max(dp[u][0]+dp[u][1])
3. 多状态转移与优化技巧
3.1 多叉树处理方案
当遇到多叉树时，常用两种处理方法：
- 左儿子右兄弟表示法：转化为二叉树处理
- 分组背包思想：将子节点看作物品组
示例代码（分组背包思路）：
cpp复制for(int v : children[u]) {