大家好，又见面了，我是全栈君。
#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
#define SIZE 230
#define BACK 1
#define AWAY 0
int DP[SIZE][SIZE][2];
bool visits[SIZE];
int vals[SIZE];
deque< int > tree[SIZE];
int num, steps;
void dfs( int u ){
visits[u] = true;
const int len = tree[u].size();
for( int i = 0; i <= steps; ++i )
DP[u][i][BACK] = DP[u][i][AWAY] = vals[u];
for( int i = 0; i < len; ++i ){
int son = tree[u][i];
if( visits[son] )
continue;
dfs( son );
for( int s = steps; s >= 0; --s ){
for( int ss = 0; ss <= s; ++ss ){
/*
从 u 出发，回到 u。须要多走两步 u->son,son->u,
分配给 son 子树 ss 步，其它子树 s - ss 步。都返回.
*/
DP[u][s + 2][BACK] = max( DP[u][s + 2][BACK],
DP[u][s - ss][BACK] + DP[son][ss][BACK] );
/*
不回 u （去 u 的其它子树）。在 son 返回.
*/
DP[u][s + 2][AWAY] = max( DP[u][s + 2][AWAY],
DP[u][s - ss][AWAY] + DP[son][ss][BACK] );
/*
先遍历 u 的其它子树，回到 u 后，遍历 son 子树，
在当前子树 son 不返回，多走一步.
*/
DP[u][s + 1][AWAY] = max( DP[u][s + 1][AWAY],
DP[u][s - ss][BACK] + DP[son][ss][AWAY] );
}
}
}
}
int main(){
int u, v;
while( cin >> num >> steps ){
memset( DP, 0, sizeof( DP ) );
memset( visits, false, sizeof( visits ) );
for( int i = 1; i <= num; ++i )
tree[i].clear();
for( int i = 1; i <= num; ++i )
cin >> vals[i];
for( int i = 1; i <= num - 1; ++i ){
cin >> u >> v;
tree[u].push_back( v );
tree[v].push_back( u );
}
dfs( 1 );
cout << max( DP[1][steps][BACK], DP[1][steps][AWAY] ) << endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116052.html原文链接：https://javaforall.net
