树形动态规划的自顶向下实现方法
树形DP基础与状态设计
树形动态规划通过自顶向下遍历树结构，将子树状态合并到父节点。核心思想是定义状态表示当前节点在不同选择下的最优解，避免贪心策略的错误。
独立集问题
定义状态：dp[u][0]表示不选节点u时子树最大权值和，dp[u][1]表示选u时的最大权值和。
状态转移：
dp[u][0] = Σ max(dp[v][0], dp[v][1])（子节点可选可不选）dp[u][1] = Σ dp[v][0] + value[u]（选u则子节点不可选）
void dfs(int node, int parent) {
dp[node][0] = 0;
dp[node][1] = node_value[node];
for (int neighbor : graph[node]) {
if (neighbor == parent) continue;
dfs(neighbor, node);
dp[node][0] += max(dp[neighbor][0], dp[neighbor][1]);
dp[node][1] += dp[neighbor][0];
}
}树形背包问题
将节点权值视为物品，容量限制为capacity。状态dp[u][w]表示以u为根的子树在容量w下的最大价值。
转移过程模拟01背包：
- 遍历子树，将子树状态合并到当前节点
- 双重循环枚举容量组合
void dfs(int node, int parent) {
memset(dp[node], -0x3f, sizeof(dp[node]));
if (weight[node] <= capacity)
dp[node][weight[node]] = profit[node];
for (int child : graph[node]) {
if (child == parent) continue;
dfs(child, node);
vector<int> temp(dp[node], dp[node] + capacity + 1);
for (int cap1 = 0; cap1 <= capacity; cap1++) {
for (int cap2 = 0; cap1 + cap2 <= capacity; cap2++) {
temp[cap1 + cap2] = max(temp[cap1 + cap2],
dp[node][cap1] + dp[child][cap2]);
}
}
for (int c = 0; c <= capacity; c++)
dp[node][c] = temp[c];
}
}最小点覆盖问题
目标：选择最少节点覆盖所有边。状态定义：
dp[u][0]：u未选，其子树被覆盖dp[u][1]：u已选，子树被覆盖
转移方程：
dp[u][0] += dp[v][1]dp[u][1] += min(dp[v][0], dp[v][1]) + 1
void dfs(int node, int parent) {
for (int child : graph[node]) {
if (child == parent) continue;
dfs(child, node);
dp[node][0] += dp[child][1];
dp[node][1] += min(dp[child][0], dp[child][1]);
}
dp[node][1] += 1;
}最小支配集问题
状态扩展为三种：
dp[u][0]：u被选，子树完全支配dp[u][1]：u未被选，但子树被支配（需至少一个子节点被选）dp[u][2]：u未被选，子树（不含u）被支配
关键转移逻辑：
dp[u][1]需保证至少一个子节点被选，通过最小差值调整
void dfs(int node, int parent) {
long long min_diff = LLONG_MAX;
for (int child : graph[node]) {
if (child == parent) continue;
dfs(child, node);
dp[node][0] += min({dp[child][0], dp[child][1], dp[child][2]});
dp[node][1] += min(dp[child][0], dp[child][1]);
min_diff = min(min_diff, dp[child][0] - min(dp[child][0], dp[child][1]));
dp[node][2] += dp[child][1];
}
dp[node][0] += node_value[node];
dp[node][1] += min_diff;
}