[Luogu-P2015] 二叉苹果树

发表于 | 更新于 | 分类于 ， ，
本文字数： 13k

链接

\(\text{Luogu-P2015 二叉苹果树}\)

题意

  有一棵苹果树，若树枝分叉，则一定分2叉，即没有只有一个子节点的节点，这棵树共\(n\)个节点，编号为1-\(n\)，树根为1。我们用一根树枝两端连接的节点的编号表示一根树枝的位置，下面是一个有四个树枝的树； 

1
2
3
4
5
2   5
 \ / 
  3   4
   \ /
    1
  现在它的枝条太多了，需要剪枝，但是每个树枝上都长有一些苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

  输入格式：第一行两个整数\(n,q\)，\(n\)表示树的节点数，\(q\)表示需要保留的树枝数量，接下来\(n-1\)行描述树枝的信息，每行三个数，前两个是它连接的结点，第三个是这跟树枝上苹果的数量，每根树枝上的苹果不超过30000个。

  数据范围：\(1\leq q\leq n,1< n\leq 100\).

  输出格式：输出一行，最多能留住的苹果的个数。

分析

  这是一个树形背包的经典入门题。

  设\(dp[x][t]\)表示在以\(x\)为根的子树中选取\(t\)个树枝，能获得的最多的苹果，\(x\)有两个子节点，如果沿一个子节点\(a\)中选了\(k\)个树枝(\(k\)个包括\(x\)与\(a\)之间的这个树枝)，那么另沿着一个子节点\(b\)则一定选了\(t-k-1\)个树枝(不包括\(b\)与\(x\)之间的这个树枝)，则动态转移方程为： \[f[u][i]=\max_{0\leq j \leq i}(f[u][i],f[u][i−j−1]+f[v][j]+a[u][v])\]

  细节见程序。

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ostream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 2000005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

int n, q, f[105][105], a[105][105];

vector<int> vec[305];

void dfs(int u, int fa) {
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        if (v == fa) continue;
        dfs(v, u);
        for (int j = q; j > 0; j--)
            for (int k = 0; k < j; k++){
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[v][k] + a[u][v]);
                //cout << u << " " << j << " " << f[u][j] << endl;
            }
    }
}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> q;
    int u, v, w;
    for (int i = 1; i <= n - 1; i++) {
        cin >> u >> v >> w;
        vec[u].push_back(v);
        vec[v].push_back(u);
        a[u][v] += w;
        a[v][u] += w;
    }
    dfs(1, 0);
    //for (int i = 1; i <= n; i++)
    //    cout << i << " " << f[i][1] << endl;
    cout << f[1][q] << endl;
}