求助站外题

Description

探险队长凯因意外的弄到了一份黑暗森林的藏宝图，于是，探险队一行人便踏上了寻 宝之旅，去寻找传说中的宝藏。 藏宝点分布在黑暗森林的各处，每个点有一个值，表示藏宝的价值。它们之间由一些 小路相连，小路不会形成环，即两个藏宝点之间有且仅有一条通路。探险队从其中的一点 出发，每次他们可以留一个人在此点开釆宝藏，也可以不留，然后其余的人可以分成若干 队向这一点相邻的点走去。需要注意的是，如果他们把队伍分成两队或者两队以上，就必 须留一个人在当前点，提供联络和通讯，当然这个人也可以一边开采此地的宝藏。并且， 为了节约时间，队伍在前往开釆宝藏的过程中是不会走回头路的。现在你作为队长的助理， 根据已有的藏宝图，请计算探险队所能开釆的最大宝藏价值。

Input

第1行有两个正整数 $n(1<=n<=100)$ 表示藏宝点的个数，$m (1<=m<=100)$ 表示探险队 的人数。 第2行是 $n$ 个不超过 $100$ 的正整数，分别表示1到n每个点的宝藏价值。 接下来的n-1行，每行两个数，$x$ 和 $y(1<=x<=y<=n )$ 表示藏宝点 $x$ 与 $y$ 之间有一条路，数据保证不会有重复的路出现。 假设一开始探险队在点 $1$ 处。

Output

一个整数，表示探险队所能获得最大的宝藏价值。

我的代码，WA,20分

#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,w[105],f[105][105],g[105][105],f1[105],g1[105];
vector <int> mp[105];

void dfs(int u,int fa){
	f[u][1]=w[u];
	for(int k=0;k<mp[u].size();k++){
		int v=mp[u][k];
		if(v==fa) continue;
		dfs(v,u);
		for(int i=1;i<=m;i++) f1[i]=max(f[u][i],f[v][i]),g1[i]=max(g[u][i],g[v][i]);
		for(int i=1;i<=m;i++) for(int j=0;j<i;j++) f1[i]=max(f1[i],g[u][i-j-1]+f[v][j]+w[u]),g1[i]=max(g1[i],g[u][i-j]+f[v][j]);
		for(int i=1;i<=m;i++) f[u][i]=f1[i],g[u][i]=g1[i];
	}
	return;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>w[i];
	for(int i=1;i<n;i++){
		cin>>u>>v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	}
	
	dfs(1,-1);
	
	cout<<f[1][m];
	return 0;
}