题目

二叉苹果树

题目描述

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树：

2   5
 \ / 
  3   4
   \ /
    1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

解题

设f[i][j]表示以i为子树中保留j个树枝能获得的最大苹果数

然后树形dp即可

不过由于这题是二叉树，所以我们可以先dfs处理出每一个节点的左右子树，然后dp的时候可以直接使用。否则要枚举i的子树并倒序循环

AC代码

#include<bits/stdc++.h>

using namespace std;

int n, q;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}
const int N = 210;

int head[N], to[N], nxt[N], edge[N], cnt = 1;
int f[N][N], size[N]/*以i为子树所含的边的数量*/, lf[N], rf[N], lf_w[N], rf_w[N];


void add(int x, int y, int z)
{
	to[++cnt] = y;
	edge[cnt] = z;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

void tongji(int u, int fa)
{
	for(int i = head[u]; i; i = nxt[i])
	{
		if(to[i] == fa) continue;
		tongji(to[i], u);
		size[u] += size[to[i]] + 1;
		if(lf[u] == 0) lf[u] = to[i], lf_w[u] = edge[i];
		else rf[u] = to[i], rf_w[u] = edge[i];
	}
}


int dp(int u, int j)
{
	if((!lf[u]) && (!rf[u])) return 0;
	if(f[u][j]) return f[u][j];
	if(j <= 0) return 0;
	int a = min(size[u], j);
	//分给左儿子 
	for(int k = 0;k <= a;k++)
	{
//		cout << u << " give left son " << k << "branches" << endl;
		if(k == 0)
		{
			f[u][j] = max(f[u][j], dp(rf[u], a - 1) + rf_w[u]);
//			cout << dp(rf[u], a - 1) + rf_w[u] << endl;
		}
		else if(a == k)
		{
			f[u][j] = max(f[u][j], dp(lf[u], a - 1) + lf_w[u]);
//			cout << dp(lf[u], a - 1) + lf_w[u] << endl;
		}
		else
		{
			f[u][j] = max(f[u][j], dp(lf[u], k - 1) + dp(rf[u], a - k - 1) + lf_w[u] + rf_w[u]);
//			cout << dp(lf[u], k - 1) + dp(rf[u], a - k - 1) + lf_w[u] + rf_w[u] << endl;
		}
	}
//	cout << u << " " << j  << ": " << f[u][j] << endl;
	return f[u][j];
}

int main()
{
	n = read(), q = read();

	int x, y, z;

	for(int i = 1;i <= n - 1;i++)
	{
		x = read(), y = read(), z = read();
		add(x, y, z);
		add(y, x, z);
	}
	tongji(1, 0);
	dp(1, q);
	cout << f[1][q];
	return 0;
}