# 11076: 【原1076】小F的苹果树

### 题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1076

## Description

2 5

\ /

3   4

\ /

1


## Input Format

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

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

## Sample Input

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


## Sample Output

21


## FineArtz's solution

/* 小F的苹果树 */
#include <iostream>
#include <set>
using namespace std;

class Node{
public:
set<int> edge;
int father = 0;
int apple = 0, sumApple = 0, sum = 0;
};

class Edge{
public:
int u = 0, v = 0, w = 0;
};

Node a[105];
Edge e[105];
int n, q;
int f[105][105] = {0};

void buildTree(int x, int f){
a[x].father = f;
for (int i : a[x].edge){
if (i != f)
buildTree(i, x);
}
}

void countApple(int x){
a[x].sumApple = a[x].apple;
a[x].sum = 1;
for (int i : a[x].edge){
if (i != a[x].father){
countApple(i);
a[x].sumApple += a[i].sumApple;
a[x].sum += a[i].sum;
}
}
}

int dp(int x, int m){
if (f[x][m] != 0)
return f[x][m];
if (m == 0){
f[x][m] = 0;
return 0;
}
if (m >= a[x].sum){
f[x][m] = a[x].sumApple;
return f[x][m];
}
if (a[x].edge.size() == 1){
f[x][m] = a[x].apple;
return f[x][m];
}
int s1 = 0, s2 = 0;
for (int i : a[x].edge){
if (i != a[x].father){
if (s1 == 0)
s1 = i;
else
s2 = i;
}
}
for (int k = 0; k < m; ++k){
f[x][m] = max(f[x][m], dp(s1, k) + dp(s2, m - k - 1) + a[x].apple);
}
return f[x][m];
}

void print(int x){
cout << x << ' ' << a[x].father << ' ' << a[x].apple << ' ' << a[x].sumApple << ' ' << a[x].sum << endl;
for (int i : a[x].edge)
if (i != a[x].father)
print(i);
}

int main(){
cin >> n >> q;
for (int i = 1; i < n; ++i){
cin >> e[i].u >> e[i].v >> e[i].w;
a[e[i].u].edge.insert(e[i].v);
a[e[i].v].edge.insert(e[i].u);
}
buildTree(1, 0);
for (int i = 1; i < n; ++i){
if (a[e[i].u].father == e[i].v)
a[e[i].u].apple = e[i].w;
else
a[e[i].v].apple = e[i].w;
}
countApple(1);
//print(1);
++q;
dp(1, q);
cout << f[1][q] << endl;
return 0;
}


## yyong119's solution

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 110;
struct Node{
int lc, rc;
int val;
};
Node tree[MAX_N];
int m, n;
int arr[MAX_N][MAX_N];
int f[MAX_N][MAX_N];
bool vis[MAX_N];

void Create(int root) {

vis[root] = true;
for (int i = 1; i <= m; ++i) {
if (!vis[i] && arr[root][i]) {
if (!tree[root].lc) tree[root].lc = i;
else tree[root].rc = i;
tree[i].val = arr[root][i];
Create(i);
}
}
}

int TreeDP(int root, int e) {

if (root == 0 || e == 0) return 0;
if (f[root][e]) return f[root][e];
int maxx = 0, l, r;
for (int i = 0; i < e; ++i) {
l = TreeDP(tree[root].lc, i);
r = TreeDP(tree[root].rc, e - i - 1);
maxx = max(l + r, maxx);
}
f[root][e] = maxx + tree[root].val;
return f[root][e];
}

int main() {

ios::sync_with_stdio(false);
cin >> m >> n;
int from, to, value;
for (int i = 1; i < m; ++i) {
cin >> from >> to >> value;
arr[to][from] = arr[from][to] = value;
}
Create(1);
cout << TreeDP(1, ++n) << endl;
return 0;
}