题目#

二叉苹果树#

题目描述#

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

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

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

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

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

解题#

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

然后树形dp即可

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

AC代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4

5
int n, q;
6

7
int read()
8
{
9
  int f = 1, x = 0;
10
  char ch = getchar();
11
  while(ch < '0' || ch > '9')
12
  {
13
    if(ch == '-') f = -1;
14
    ch = getchar();
15
  }
16

17
  while(ch >= '0' && ch <= '9')
18
  {
19
    x = x * 10 + ch - '0';
20
    ch = getchar();
21
  }
22
  return f * x;
23
}
24
const int N = 210;
25

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

29

30
void add(int x, int y, int z)
31
{
32
  to[++cnt] = y;
33
  edge[cnt] = z;
34
  nxt[cnt] = head[x];
35
  head[x] = cnt;
36
}
37

38
void tongji(int u, int fa)
39
{
40
  for(int i = head[u]; i; i = nxt[i])
41
  {
42
    if(to[i] == fa) continue;
43
    tongji(to[i], u);
44
    size[u] += size[to[i]] + 1;
45
    if(lf[u] == 0) lf[u] = to[i], lf_w[u] = edge[i];
46
    else rf[u] = to[i], rf_w[u] = edge[i];
47
  }
48
}
49

50

51
int dp(int u, int j)
52
{
53
  if((!lf[u]) && (!rf[u])) return 0;
54
  if(f[u][j]) return f[u][j];
55
  if(j <= 0) return 0;
56
  int a = min(size[u], j);
57
  //分给左儿子
58
  for(int k = 0;k <= a;k++)
59
  {
60
//    cout << u << " give left son " << k << "branches" << endl;
61
    if(k == 0)
62
    {
63
      f[u][j] = max(f[u][j], dp(rf[u], a - 1) + rf_w[u]);
64
//      cout << dp(rf[u], a - 1) + rf_w[u] << endl;
65
    }
66
    else if(a == k)
67
    {
68
      f[u][j] = max(f[u][j], dp(lf[u], a - 1) + lf_w[u]);
69
//      cout << dp(lf[u], a - 1) + lf_w[u] << endl;
70
    }
71
    else
72
    {
73
      f[u][j] = max(f[u][j], dp(lf[u], k - 1) + dp(rf[u], a - k - 1) + lf_w[u] + rf_w[u]);
74
//      cout << dp(lf[u], k - 1) + dp(rf[u], a - k - 1) + lf_w[u] + rf_w[u] << endl;
75
    }
76
  }
77
//  cout << u << " " << j  << ": " << f[u][j] << endl;
78
  return f[u][j];
79
}
80

81
int main()
82
{
83
  n = read(), q = read();
84

85
  int x, y, z;
86

87
  for(int i = 1;i <= n - 1;i++)
88
  {
89
    x = read(), y = read(), z = read();
90
    add(x, y, z);
91
    add(y, x, z);
92
  }
93
  tongji(1, 0);
94
  dp(1, q);
95
  cout << f[1][q];
96
  return 0;
97
}