求最大權(quán)值的子樹(shù)
dp[root][i] = MAX{dp[root][j] + dp[child][i – j]}
其中 K >= i >= 2
表示以root為根，節(jié)點(diǎn)數(shù)為i 的子樹(shù)的最大權(quán)值
1
#include <cstdio>
2
3const int SIZE = 101;
4
5struct TREE
6
{
7
int m_arr[SIZE];
8 int m_size;
9 int m_value;
10
}tree[SIZE];
11
12int N, K;
13int dp[SIZE][SIZE];
14
15inline int MAX(const int& a, const int& b)
16{
17 return (a > b ? a : b);
18}
19
20void Init()
21{
22 int i;
23 for ( i = 0; i < SIZE; ++i )
24 tree[i].m_size = 0;
25}
26
27void 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
59void 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
72int 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}