树形DP入门详解+题目推荐

2023-08-18 15:36:16

树形DP。这是个什么东西？为什么叫这个名字？跟其他DP有什么区别？

相信很多初学者在刚刚接触一种新思想的时候都会有这种问题。

没错，树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。

既然说了这是一种思想，那么单讲的话，也讲不出什么东西来。所以我们结合具体题目进行讲解，希望大家可以在题目中领悟这种思想。

提到树形DP入门题，很多人都会提到没有上司的舞会这道题，的确，这道题堪称树形DP的典范，但是我个人认为，这道题的处理方式不够普遍，二叉苹果树这道题的处理方式相比之下更加普遍。下面我们就将结合这道题进行讲解。

题意很简单，每条边有一个权值，保留若干条边，求去掉边后根节点能够到达的所有边的权值和最大是多少。

看到这道题，也许大家会想到数字三角形这道题，但是这里的这棵树并不是一颗满二叉树，甚至也不是一颗完全二叉树，所以我们不能用数字三角形的处理方式来做这道题。那该怎么思考呢？很明显，这是一个树状结构，我们可以从这点出发来考虑。这道题明确给出了根的位置，也就确定了父子节点的关系，我们会发现，对于每个父节点的状态，都是由它的子节点转移过来的，所以我们大概可以得出这里有一个由子节点转移到父节点的状态转移方程，又因为父节点子树上选择的边数完全取决于子节点的子树选择的边数。

\(f[u][i]=max(f[u][i],f[u][i−j−1]+f[v][j]+w)\)

\(f[u][i]\)表示以\(u\)为根节点的子树选择\(i\)条边权值和最大为多少，这实际上就是一个背包。为什么两个\(f\)数组的边数为\(i-1\)条呢？因为我们若想取一颗子节点的子树上的边，那就必须取父节点与子节点相连的那条边。

我们下面来看代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc getchar

#define maxn 105

using namespace std;

inline ll read(){

	ll a=0;int f=0;char p=gc();

	while(!isdigit(p)){f|=p=='-';p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}

struct ahaha{

	int w,to,next;

}e[maxn<<1];int tot,head[maxn];

inline void add(int u,int v,int w){

	e[tot].w=w,e[tot].to=v,e[tot].next=head[u];head[u]=tot++;

}int n,m;

int sz[maxn],f[maxn][maxn];

void dfs(int u,int fa){

	for(int i=head[u];~i;i=e[i].next){

		int v=e[i].to;if(v==fa)continue;

		dfs(v,u);sz[u]+=sz[v]+1;  //子树边数在加上子节点子树的基础上还要加一，也就是连接子节点子树的那条边

		for(int j=min(sz[u],m);j;--j)   //由于是01背包，所以要倒序DP

			for(int k=min(j-1,sz[v]);k>=0;--k)    //这一维正序倒序无所谓，但是把取min放在初始化里可以减少运算次数，算是一个优化的小习惯

				f[u][j]=max(f[u][j],f[u][j-k-1]+f[v][k]+e[i].w);

	}

}

int main(){memset(head,-1,sizeof head);

	n=read();m=read();

	for(int i=1;i<n;++i){    //前向星存边，要存两边，便于读取

		int u=read(),v=read(),w=read();

		add(u,v,w);add(v,u,w);

	}

	dfs(1,-1);

	printf("%d",f[1][m]);

	return 0;

}