#创作计划# 树形dp
2026-05-05 14:38:55
发布于：广东
前言
依旧学到哪写到哪，依旧草履虫都能学会，依旧简单语言，依旧被 Xylophone 压力。
正文
What is...
树形 DP，即在树上进行的 DP．由于树固有的递归性质，树形 DP 一般都是递归进行的． ——OI Wiki[1]
实现
问，为什么这么早就上例题？
答，不上例题没办法讲。
B2171 结点子树大小 / 依旧没有 ACGO 版本，哎呦我这不 ACGO 叔叔吗。
题目大意
给定一棵 个节点的树，其中根结点编号为 。
然后，给定 条边（保证构成树），输入格式 ，表示一条 到 的边。
求出每一节点的子树大小（包含当前节点）。
思路
注意到每个节点的子树大小都包含了自己+所有子树的大小，而叶子节点没有子树，所以子树大小只包含自身，即 。
那么可以对于每一个非叶节点先处理子节点的子树大小，然后在自己的子树大小加上这个子节点的子树大小。
因为树的递归性质，我们可以递归处理子树。同时，还要多一个父节点参数来防止走回去。
对于根节点，我们在递归时给他来一个假爹 ，这样就能给根节点传 父节点 参数了。
那么递归的结束条件呢？很简单，当递归到叶子节点时，由于没有子节点，递归不会继续，变相实现了递归结束条件。
代码（参考注释食用）
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
vector<int> g[N];//邻接表
vector dp(N,0);//dp 数组
void dfs(int u,int fa){//u 为当前节点，fa 为父节点
dp[u] = 1;//包含当前节点
for(int v : g[u]){
if(v==fa) continue;
dfs(v,u);
dp[u] += dp[v];
}
}
int main(){
int n;cin >> n;
for(int i = 1;i < n;i++){
int u,v;cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
for(int i = 1;i <= n;i++) cout << dp[i] << ' ';
}
例题，例题和例题，当然还有例题
P1352 没有上司的舞会 / A41048.【树形动态规划】没有上司的舞会
先处理子节点的最大值，再处理当前节点。
考虑给dp数组多开一个维度，dp[i][0]表示 不参加的最大值，dp[i][1]表示 参加的最大值。
转移方程（v代表子节点）：
- 当 参加时，其直接下属不能参加，所以只能加上不参加的结果
dp[v][0]; - 当 不参加时，其直接下属可以选择参加或不参加，所以在两种结果取最大值：
max(dp[v][0],dp[v][1])。
dp[u][1]+=dp[v][0];
dp[u][0]=max(dp[v][1],dp[v][0]);
遍历v求解即可，注意要找根。
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
vector<int> g[N];//邻接表
int r[N],dp[N][2];//dp 数组
void dfs(int u){//u 为当前节点
dp[u][1] = r[u];
for(int v : g[u]){
dfs(v);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][0],dp[v][1]);
}
}
int main(){
int n;cin >> n;
vector<bool> flag(N,1);
for(int i = 1;i <= n;i++) cin >> r[i];
for(int i = 1;i < n;i++){
int u,v;cin >> u >> v;
g[v].push_back(u);
flag[u]=0;
}
int root = 0;
for(int i = 1;i <= n;i++){
if(flag[i]==1) root = i;
}
dfs(root);
cout << max(dp[root][1],dp[root][0]);
}
不加注释是因为带注释版本一个刷新被洛谷吃了。
----例题持续更新中，有意见请提出----
全部评论 3
Xyl 怎么还不来，看我呼唤一下：整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分整体二分
1周前 来自 浙江
1
有帮助，赞一个