loj 10153. 「一本通 5.2 例 1」二叉苹果树

题面

一本通上树形动规的第一道例题，本质上是一个背包问题

用 $f_{u,~i}$ 表示在第 $u$ 棵子树上，选取 $i$ 条边时能获得的最大价值

那么就有状态转移方程：

$$f_{u,~i}=\max(f_{u,~i},f_{u,~i-j-1}+f_{v,~j}+e[i].val)$$

对于结点 $u$，dfs枚举它的每一棵子树 $v$。 $f_{u,~i}$ 为 $u$ 结点选择 $i$ 条边的价值。它可以用 $v$ 结点选择 $j$ 条边的价值加上 $v$ 结点先前选的 $i-j-1$ 条边的价值来更新。减去1是因为一旦选择了子树 $v$，那么 $u$ 与 $v$ 相连的边也要选中。

---

接着我们就可以根据以上这些写出代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=103;
int n,m,cnt,head[maxn],sz[maxn],f[maxn][maxn<<1];
struct Edge{
	int to,val,nxt;
}a[maxn<<1];
void add(int x,int y,int z) {a[++cnt]=(Edge){y,z,head[x]}; head[x]=cnt;}
void dfs(int x,int fa){
	for(int i=head[x];i;i=a[i].nxt){        //每棵子树
		if(a[i].to==fa) continue;
		dfs(a[i].to,x);                         //向下dfs
		sz[x]+=sz[a[i].to]+1;               //更新当前结点size
		for(int j=min(sz[x],m);j>=0;j--){ //当前结点选择j条边
			for(int k=min(sz[a[i].to],j-1);k>=0;k--)    //枚举子树上选择k条边
				f[x][j]=max(f[x][j],f[x][j-k-1]+f[a[i].to][k]+a[i].val);
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,x,y,z;i<=n-1;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z),add(y,x,z);
	}
	dfs(1,0);
	printf("%d\n",f[1][m]);
	return 0;
}