20250927树形DP
引子
树形DP是一种在树上的动态规划，利用树的递归特性在树上进行状态转移。
树状DP主要分为两类：
- 独立型：兄弟节点间无相互约束
- 依赖型：兄弟节点间存在相互约束
独立型树状DP的特点是兄弟节点的状态互不影响，各自独立计算。就比如没有上司的舞会。
依赖型树状DP则表现为兄弟节点状态之间存在制约关系，状态分配需要权衡取舍（如资源分配问题）。就比如二叉苹果树。
H P1352 没有上司的舞会
简化题意：有 n 个点，他们的从属关系用一颗树来表示，父结点是子结点的直接上司。每个点有一个点权，求拿出若干个点且这若干个点的任意两点无从属关系的最大点权和。
我们定义状态dp[i][0/1]表示以节点𝑖为根的子树的最大点权值。其中：
- 第二维取0表示节点 i 不参加舞会
- 第二维取1表示节点 i 参加舞会
状态转移方程如下（设 v 为 x 的子节点）：
- 当 x 不参加舞会时：
dp[x][0]+=max(dp[v][1],dp[v][0]);
即子节点可以自由选择是否参加 - 当 x 参加舞会时：
dp[x][1]+=dp[v][0];
此时所有子节点都不能参加
我们用DFS遍历这棵树，在回溯时更新每个节点的DP。
#include<bits/stdc++.h>usingnamespacestd;intr[6005],dp[6005][2];vector<int>E[6005];voiddfs(intx,intfa){dp[x][1]=r[x];for(inti=0;i<E[x].size();i++){intv=E[x][i];if(v==fa)continue;dfs(v,x);dp[x][0]+=max(dp[v][1],dp[v][0]);dp[x][1]+=dp[v][0];}}intmain(){intn;cin>>n;for(inti=1;i<=n;i++){cin>>r[i];}for(inti=1;i<n;i++){intu,v;cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}dfs(1,0);cout<<max(dp[1][0],dp[1][1]);return0;}J P2015 二叉苹果树
题意：给定一棵树，n 个点，有边权，至少保留 q 条边，求最大边权和。
1.q 条边分到左子树多，那么右子树就少，兄弟节点间有数量约束，考虑第二类树型DP。
2.状态:dp[i][j]表示以 i 为根节点的子树保留至多 j 条边的最大边权和。
3.答案:dp[1][q]
4.状态转移：
intv=E[x][i].v,w=E[x][i].w;if(v==fa)continue;dfs(v,x);sz[x]+=sz[v];for(intj=min(q,sz[x]);j>=0;j--){for(intk=0;k<=min(j-1,sz[v]);k++){dp[x][j]=max(dp[x][j],dp[v][k]+dp[x][j-k-1]+w);}}5.初始状态:dp[x][0]=0
#include<bits/stdc++.h>usingnamespacestd;structnode{intu,v,w;};vector<node>E[105];intn,q,sz[105],dp[105][105];voiddfs(intx,intfa){sz[x]=1;for(inti=0;i<E[x].size();i++){intv=E[x][i].v,w=E[x][i].w;if(v==fa)continue;dfs(v,x);sz[x]+=sz[v];for(intj=min(q,sz[x]);j>=0;j--){for(intk=0;k<=min(j-1,sz[v]);k++){dp[x][j]=max(dp[x][j],dp[v][k]+dp[x][j-k-1]+w);}}}}intmain(){cin>>n>>q;for(inti=1;i<n;i++){intu,v,w;cin>>u>>v>>w;E[u].push_back({u,v,w});E[v].push_back({v,u,w});}dfs(1,0);cout<<dp[1][q];return0;}