二叉苹果树

给定一棵n个结点的二叉树，你需要选择一棵以1号结点为根，m条边的联通子树，使得所选择的边权值之和最大。

输入描述:

第一行两个整数n,m。
之后n-1行，每行三个整数x,y,z，表示结点x,y之间有一条权值为z的无向边。

输出描述:

所选的边的权值和的最大值。

示例1
输入

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

输出

21

说明

n<=100, m<=n-1.

erchapingguo1.cppview raw

//70%
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 110;
int n, m;

struct Node{
    int to, val;
};
vector<Node> edge[N];
int ch[N][2];
int dp[N][N];
int val[N];

void dfs(int x, int f){
    int k=0;
    for(int i=0;i<edge[x].size();i++){
        int y = edge[x][i].to;
        if(y!=f){
            dfs(y, x);
            val[y] = edge[x][i].val;
            ch[x][k++] = y;
        }
    }
//    printf("%d %d\n", x, k);
}

void DP(int x){
    int ls = ch[x][0];
    int rs = ch[x][1];
    if(ls==0 && rs==0){
        for(int i=1;i<=m;i++) dp[x][i] = val[x];
        return;
    }
    if(ls!=0 && rs!=0) {
        DP(ls);
        DP(rs);
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j + 1 <= i; j++)
                dp[x][i] = max(dp[x][i], dp[ls][j] + dp[rs][i - j - 1] + val[x]);
        }
    }
}

int main(){
    scanf("%d%d", &n, &m); m++;
    for(int i=1;i<=n-1;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[a].push_back({b, c});
        edge[b].push_back({a, c});
    }

    dfs(1, 0);
    DP(1);
    printf("%d\n", dp[1][m]);
    return 0;
}

erchapingguo2.cppview raw

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 110;
int n, m;

struct Node{
    int to, val;
};
vector<Node> edge[N];
int ch[N][2];
int dp[N][N];
int val[N];

void dfs(int x, int f){
    int k=0;
    for(int i=0;i<edge[x].size();i++){
        int y = edge[x][i].to;
        if(y!=f){
            dfs(y, x);
            val[y] = edge[x][i].val;
            ch[x][k++] = y;
        }
    }

    if(k!=0){
        int ls = ch[x][0];
        int rs = ch[x][1];
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j <= i; j++)
                dp[x][i] = max(dp[x][i], dp[ls][j] + dp[rs][i - j]);
        }
    }
    for(int i=m;i>=1;i--)
        dp[x][i] = dp[x][i-1] + val[x];
}


int main(){
    scanf("%d%d", &n, &m); m++;
    for(int i=1;i<=n-1;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[a].push_back({b, c});
        edge[b].push_back({a, c});
    }

    dfs(1, 0);
    printf("%d\n", dp[1][m]);
    return 0;
}

duochapingguo.cppview raw

// Note that m edges rather than m nodes.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

const int N = 110;
int n, m;

struct Node{
    int to, val;
};
vector<Node> edge[N];
int dp[N][N];
int tmp[N];
int sz[N];

void dfs(int x, int f){
    for(int i=0;i<edge[x].size();i++){
        int y = edge[x][i].to, val = edge[x][i].val;
        if (y==f) continue;
        dfs(y, x);
        sz[x] += sz[y] + 1;
        memset(tmp, 0, sizeof tmp);
        int mi= min(sz[x], m);
        for(int j=0;j<=mi;j++)
            for(int t=1;t<=j;t++) // t个分给新儿子用,j-t给之前儿子用
                tmp[j] = max(tmp[j], dp[y][t-1] + dp[x][j-t] + val);
        for(int j=1;j<=m;j++) dp[x][j] = max(dp[x][j], tmp[j]);
    }
}


int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n-1;i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edge[a].push_back((Node){b, c});
        edge[b].push_back((Node){a, c});
    }

    dfs(1, 0);
    printf("%d\n", dp[1][m]);
    return 0;
}