- BC20260025's blog
11.27信息笔记（树形DP）
-
BC20260025
LV 6
@
2024-11-27 10:00:04
树形DP
简介
经典应用：树的重心（以这个点为根，最大子树的结点数最少），树的直径，树的中心（到树中其他点的最远距离最近）
问题：给定一棵树，从中选择最少的结点，使得所有边至少有一个端点在所选集合中，输出所选择结点的个数。（本题其实是）
分析：主要是点的取舍，用dp[i][1]和dp[i][0]分别表示该点取或不取时，以它为根的子树的最小代价。
转移：如果该点不取，则必须取它的所有儿子，此时 ；否则，选取最优解，此时 $ dp[i][1]=1+\sum_{j \in son[i]} \min(dp[j][1],dp[j][0]) $。转移方向是从叶子结点到根结点，可以使用递归实现。
例题
- 树的直径（洛谷B4016）
- 没有上司的舞会
思路类似简介中的问题
代码
# include<iostream>
using namespace std;
const int N=6e3+5;
int n,r[N],dp[N][2],l,k,root;
int cnt,head[N],to[N],nxt[N];
bool f[N],vis[N];
void add(int x,int y){
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
void dfs(int x){
if(vis[x]) return;
vis[x]=1;
for(int i=head[x];i;i=nxt[i]){
int y=to[i];
dfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
}
dp[x][1]+=r[x];
}
int main(){
cin>>n;
root=n*(n+1)/2;
for(int i=1;i<=n;++i) cin>>r[i];
for(int i=1;i<n;++i){
cin>>l>>k;
add(k,l);
root-=l;
}
dfs(root);
cout<<max(dp[root][0],dp[root][1]);
return 0;
}
- 二叉苹果树
需要留意到一点：这是一棵现实意义上的树，因此树根 需要被保留，且修剪完之后必须是一个连通块。
用 和 分别代表结点x的左右儿子， 代表结点x和y之间的边权， 表示 号结点的子树保留 根树枝的最大苹果数量，那么可以得到转移：
其中：
$$s=\begin{cases} 0 & p=0 \\ dp[l[x]][p-1]+w[x][l[x]] & p\ge 1 \end{cases}$$$$t=\begin{cases} 0 & q=0 \\ dp[r[x]][q-1]+w[x][r[x]] & q\ge 1 \end{cases}$$时间复杂度 ，空间复杂度 ，在本题 的限制下可以通过。
（本题实敲50min。。。）
代码
# include<iostream>
using namespace std;
const int N=105;
int n,q,x,y,z;
bool vis[N];
int map[N][N],to[N][5];
int l[N],r[N],fa[N],son[N];
int dp[N][N],tmp;
void build(int x){
if(to[x][0]==1){
son[x]=1;
return;
}
if(x==1){
l[x]=to[x][1];
r[x]=to[x][2];
}
else{
if(to[x][1]==fa[x]){
l[x]=to[x][2];
r[x]=to[x][3];
}
else if(to[x][2]==fa[x]){
l[x]=to[x][3];
r[x]=to[x][1];
}
else{
l[x]=to[x][1];
r[x]=to[x][2];
}
}
fa[l[x]]=fa[r[x]]=x;
build(l[x]);
build(r[x]);
son[x]=son[l[x]]+son[r[x]]+1;
return;
}
void dfs(int x){
if(son[x]==1) return;
dfs(l[x]);
dfs(r[x]);
for(int i=0;i<=son[l[x]];++i)
for(int j=0;j<=son[r[x]];++j){
tmp=0;
tmp+=(i?dp[l[x]][i-1]+map[x][l[x]]:0);
tmp+=(j?dp[r[x]][j-1]+map[x][r[x]]:0);
dp[x][i+j]=max(dp[x][i+j],tmp);
}
}
int main(){
cin>>n>>q;
for(int i=1;i<n;++i){
cin>>x>>y>>z;
map[x][y]=z;
map[y][x]=z;
to[x][++to[x][0]]=y;
to[y][++to[y][0]]=x;
}
build(1);
dfs(1);
cout<<dp[1][q];
return 0;
}