树形DP
高级树形 DP 是 CSP-S 高频考点，核心是"子树信息合并"。
// 算法讲解
树形DP
演示树形DP求解树上最大独立集的过程。
待机
速度 中
待机 ⌨1int dp[100001][2];
2
3void dfs(int u, vector<vector<int>>& adj, vector<int>& val) {
4 dp[u][0] = 0;
5 dp[u][1] = val[u];
6 for (int v : adj[u]) {
7 dfs(v, adj, val);
8 dp[u][0] += max(dp[v][0], dp[v][1]);
9 dp[u][1] += dp[v][0];
10 }
11}
复杂度分析
时间 O(n)
空间 O(n)
最优 O(n)
最坏 O(n)
算法讲解
树形 DP 在树上定义 DP 状态，通常以子树为单位进行转移。
经典问题：树的最大独立集、树的直径、树上最长路径。
实现方式：后序遍历（DFS），先处理子树再合并到父节点。
时间复杂度 O(n)，空间复杂度 O(n)。