f[i][j]表示以i為根含j個(gè)節(jié)點(diǎn)的總重。
f[i][j+k]=max(f[i][j+k],f[i][j]+f[i.son[t]][k])。
ZOJ 3201
#include<iostream>
using namespace std;
int T[110][110],w[110];
int f[110][201];
bool v[110];
int n,p;
void DFS(int root)
{
if(v[root]==1)
return ;
v[root]=1;
int i,j,k;
for(i=1;i<=T[root][0];i++)
DFS(T[root][i]);
f[root][1]=w[root];
for(i=1;i<=T[root][0];i++)
{
for(j=p;j>=1;j--)
if(f[root][j]!=-1)
{
for(k=1;k<=p;k++)
{
if(f[T[root][i]][k]!=-1)
{
f[root][j+k]=max(f[root][j+k],f[root][j]+f[T[root][i]][k]);
}
}
}
}
return ;
}
int DP()
{
memset(f,-1,sizeof(f));
memset(v,0,sizeof(v));
DFS(0);
int maxx=0;
int i;
for(i=0;i<n;i++)
{
if(maxx<f[i][p])
maxx=f[i][p];
}
return maxx;
}
int main()
{
while(scanf("%d%d",&n,&p)!=EOF)
{
memset(T,0,sizeof(T));
int i;
for(i=0;i<n;i++)
scanf("%d",&w[i]);
int a,b;
for(i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
T[a][++T[a][0]]=b;
T[b][++T[b][0]]=a;
}
printf("%d\n",DP());
}
return 0;
}