求最大权值的子树
dp[root][i] = MAX{dp[root][j] + dp[child][i – j]}
其中 K >= i >= 2
表示以root为根,节点数为i 的子树的最大权值
1
#include <cstdio>
2
3
const int SIZE = 101;
4
5
struct TREE
6

{
7
int m_arr[SIZE];
8
int m_size;
9
int m_value;
10
}tree[SIZE];
11
12
int N, K;
13
int dp[SIZE][SIZE];
14
15
inline int MAX(const int& a, const int& b)
16

{
17
return (a > b ? a : b);
18
}
19
20
void Init()
21

{
22
int i;
23
for ( i = 0; i < SIZE; ++i )
24
tree[i].m_size = 0;
25
}
26
27
void DFS( const int& root, const int& fat )
28

{
29
int i, j, k;
30
31
dp[root][0] = 0;
32
dp[root][1] = tree[root].m_value;
33
for ( i = 2; i <= K; ++i )
34
dp[root][i] = -1;
35
36
for ( i = 0; i < tree[root].m_size; ++i )
37
{
38
int x = tree[root].m_arr[i];
39
40
if ( x == fat )
41
continue;
42
43
DFS( x, root );
44
45
for ( j = K; j >= 2; --j )
46
{
47
int t = -1;
48
for ( k = 1; k <= j; ++k )
49
{
50
if ( dp[root][k] == -1 || dp[x][j - k] == -1 )
51
continue;
52
t = MAX( t, dp[root][k] + dp[x][j - k] );
53
}
54
dp[root][j] = t;
55
}
56
}
57
}
58
59
void Solve()
60

{
61
int ans = 0;
62
63
DFS( 0, -1 );
64
65
for ( int i = 0; i < N; ++i )
66
if ( ans < dp[i][K] )
67
ans = dp[i][K];
68
69
printf("%d\n", ans);
70
}
71
72
int main()
73

{
74
//freopen("1.txt", "r", stdin);
75
76
int i, x, y;
77
78
while ( scanf("%d %d", &N, &K) != EOF )
79
{
80
Init();
81
82
for ( i = 0; i < N; ++i )
83
scanf("%d", &tree[i].m_value);
84
85
for ( i = 0; i < N - 1; ++i )
86
{
87
scanf("%d %d", &x, &y);
88
tree[x].m_arr[tree[x].m_size++] = y;
89
tree[y].m_arr[tree[y].m_size++] = x;
90
}
91
92
Solve();
93
}
94
95
return 0;
96
}