P2015 二叉苹果树

题目描述

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

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

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

1
2
3
4
5
2   5
 \ / 
  3   4
   \ /
    1

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

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

输入格式

第1行2个数，$N$ 和 $Q$($1\leq Q\leq N,1<N\leq100$)。

$N$ 表示树的结点数，$Q$ 表示要保留的树枝数量。接下来 $N-1$ 行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

输出格式

一个数，最多能留住的苹果的数量。

输入输出样例

输入 #1

1
2
3
4
5
5 2
1 3 1
1 4 10
2 3 20
3 5 20

输出 #1

1
21

解决方案：

啊，树形dp入门题，按照深度优先的顺序去遍历树，在过程中进行dp。

很容易想到，按照每个节点作为一颗子树去进行dp，设状态为 $dp(u, i)$， 其中 $u$ 为当前节点的编号， $i$ 为当前节点为子树，保留 $i$ 条边，则 $dp(u, i)$ 显然为此时保留的最大的🍎的数量。

如何进行状态转移？既然都叫树形dp，肯定是由其子节点转移而来。想象一下这个dp过程，把 $u$ 的孩子节点的为根的子树一棵一棵加进来，去更新 $dp(u, i)$ 的值。

例如，假设要保留 3 条边，1 为根节点，1 的孩子节点为 2, 3, 4.

那么刚开始的时候 1 为根节点的树是空树，由于我们是按照深度优先去进行dp的，所以

$dp[i][j],i \in [2, 4], j \in [0, 3]$ 的值都是已经求出来的了。先把 2 为根的子树加进去，更新

$dp[1][j], j \in [0, 3]$， 然后再把 3， 4 一个一个加进去，利用孩子节点的dp值更新父节点，这就是此题的基本思路。

状态转移方程为：

其中：

其实这题完全可以拓展至多叉树或者无根树，代码几乎不需要变动。

更多细节看代码里的注释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;

struct edge {
  int to, co, nxt;
};

int dp[maxn][maxn];  // dp{i, j}， 当前节点编号，保留的边数
edge e[2 * maxn];
int head[maxn];
int num[maxn];  // 编号为 i 的节点为根的子树有多少条边
int tot;
int n, q;

void add_edge(int ff, int tt, int cc) {
  e[tot] = edge{tt, cc, head[ff]};
  head[ff] = tot++;
  e[tot] = edge{ff, cc, head[tt]};
  head[tt] = tot++;
}

void dfs(int u, int fa) {
  for (int i = head[u]; i != -1; i = e[i].nxt) {
    int v = e[i].to;
    if (v == fa) {  // 遇到父节点跳过
      continue;
    }
    dfs(v, u);             // 按照深度优先，先dfs孩子节点
    num[u] += num[v] + 1;  // dfs的同时求一下该点为根节点子树的边数

    // 为什么当前保存的边数 j 要倒着dp？和01背包的滚动数组类似，
    // dp[u][j]在更新后，不会在后面的更新中用到，而正着dp就会出问题了，
    // 那样你会用到在加入 v 子节点后，被更新过的dp[u][j]的值，显然是错误的
    for (int j = min(num[u], q); j >= 0; j--) {
      // k正着反着倒无所谓
      // 这里有个细节，为什么 k 取的是min{num[v], j - 1}而不是min{num[v], j}?
      // 因为，既然我要把点 v 加进来，那肯定是要有一条边把 u 和 v
      // 连起来，那条边就是e[i]，所以 k 最多取的是min{num[v], j - 1}
      for (int k = min(num[v], j - 1); k >= 0; k--) {
        dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + e[i].co);
      }
    }
  }
}

int main() {
  memset(head, -1, sizeof(head));
  scanf("%d%d", &n, &q);
  for (int i = 0; i < n - 1; i++) {
    int ff, tt, cc;
    scanf("%d%d%d", &ff, &tt, &cc);
    add_edge(ff, tt, cc);
  }
  dfs(1, -1);
  printf("%d\n", dp[1][q]);
  return 0;
}

快开学了T_T