P2015 Binary Apple Tree

Problem#

Binary Apple Tree#

Problem Description#

There is an apple tree, and if the branches have forks, they must be binary (meaning there are no nodes with only one child).

This tree has a total of $N$ nodes (leaf nodes or branch fork nodes), numbered from $1$ to $N$, with the root node numbered as $1$.

We describe the position of a branch using the node numbers at both ends of the branch. Below is a tree with $4$ branches:

Now there are too many branches on this tree, and it needs to be pruned. However, some branches bear apples.

Given the number of branches that need to be retained, determine the maximum number of apples that can be kept.

Solution#

Let f[i][j] represent the maximum number of apples that can be obtained by retaining j branches in the subtree rooted at i.

Then we can use tree dynamic programming.

However, since this problem involves a binary tree, we can first perform a DFS to process each node's left and right subtrees, and then we can directly use them in the DP. Otherwise, we would have to enumerate the subtree of i and loop in reverse.

AC Code#

#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]/*number of edges in the subtree rooted at 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);
	// Give to left child 
	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;
}