题目链接:传送门

Description

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点） 这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。

Solution

这又是一道树形DP的经典题目。 我们设

TeX parse error: Undefined control sequence \[

表示以x为节点的根保留j条树枝的最大值，k表示枚举y子树保留k根树枝，那么有：

TeX parse error: Undefined control sequence \[

我们只需要dfs一遍，枚举j和k即可

Code

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define begin Begin
#define next Next
using namespace std;
const int maxn=100+10;
int n,m,e;
int begin[maxn],to[maxn*2],next[maxn*2],w[maxn*2];
inline void add(int x,int y,int z){
    to[++e]=y;
    next[e]=begin[x];
    begin[x]=e;
    w[e]=z;
}
int p[maxn],f[maxn][maxn];
inline int dfs(int x){
    int son=0;
    for(int i=begin[x];i;i=next[i]){
        int y=to[i];
        if(p[y])continue;
        p[y]=1;
        son+=dfs(y)+1;
        for(int j=min(son,m);j>=1;j--)
            for(int k=min(m,j);k>=1;k--)
                f[x][j]=max(f[x][j],f[x][j-k]+f[y][k-1]+w[i]);
    }
    return son;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    p[1]=1;
    dfs(1);
    printf("%d\n",f[1][m]);
    return 0;
}