[Acwing&luogu] P2015 二叉苹果树 树形DP+有依赖的背包问题

前言

Acwing传送门 : Luogu传送门 :

思路

这题看完,感觉和上一篇的有依赖的背包问题 差不多

只不过这题是边权,那题是点权,但是又因为是树,每一个节点

的父节点有且只有一个,所以边权可以当作点权

因此思路还是差不多 :

状态表示 : f [ u ] [ k ] f[u][k] f[u][k] 表示以 u u u为根节点,选取 k k k条边的最大价值

状态计算 : f [ u ] [ k ] = m a x ( f [ u ] [ k ] , f [ u ] [ j − k − 1 ] + f [ s o n ] [ k ] + w [ i ] ) f[u][k] = max(f[u][k],f[u][j-k-1]+f[son][k]+w[i]) f[u][k]=max(f[u][k],f[u][j−k−1]+f[son][k]+w[i])

为什么是 k − 1 k-1 k−1? 因为根节点必须选,但是根节点没有父节点,也就是少一条边,所以我们需要 − 1 -1 −1

CODE

int f[N][N];


void dfs(int u,int fa)
{
	for(auto i : g[u])
	{
		if(i.to == fa)
		continue;
	
		dfs(i.to,u);
		//计算到底部,再使用状态计算
		
		for(int j = m;j>=0;j--)
		{
			for(int k = 0 ;k>n>>m;
	for(int i=1;i>a>>b>>c;
		g[a].push_back({b,c});
		g[b].push_back({a,c});
	}
	
	dfs(1,-1);
	cout