http://poj.org/problem?id=2486
#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
int value[100];
int gone[100][201],m,K,n;
int back[100][201];
list<int> e[100];
void merge_back(int bk1[], int bk2[], int bk[], int maxstep )
{
int i,j;
for( i=0; i<=maxstep; i++ )
{
bk[i] = bk2[i];
for( j=2; j<=i; j++ )
if( bk1[j-2] + bk2[i-j] > bk[i] )
bk[i] = bk1[j-2] + bk2[i-j];
}
return ;
}
void merge_gone(int go1[], int bk1[], int go2[], int bk2[], int go[], int maxstep )
{
int i,j;
for( i=0; i<=maxstep; i++ )
{
go[i] = go2[i];
for( j=1; j<=i; j++ )
if( go1[j-1] + bk2[i-j] > go[i] )
go[i] = go1[j-1] + bk2[i-j];
for( j=2; j<=i; j++ )
if( bk1[j-2] + go2[i-j] > go[i] )
go[i] = bk1[j-2] + go2[i-j];
}
return ;
}
int back_temp[201],gone_temp[201];
void calculate(int root,int maxstep,int father)
{
int i,j;
list<int>::iterator iter;
if( root>100 || root<0 )
int *p = new int[10000000];
for( i=0; i<=maxstep ; i++ )
{
gone[root][i] = back[root][i] = value[root];
}
if( maxstep == 0 ) return ;
for( iter = e[root].begin(); iter != e[root].end() ; iter++ )
if( *iter != father )
{
calculate( *iter, maxstep-1 , root );
merge_back( back[*iter], back[root], back_temp, maxstep );
merge_gone( gone[*iter], back[*iter], gone[root], back[root], gone_temp,maxstep );
copy( back_temp, back_temp+maxstep+1, back[root] );
copy( gone_temp, gone_temp+maxstep+1, gone[root] );
}
}
bool init()
{
int i, a, b;
cin>>n>>K;
if( n>100 || K>200 )
while(cout<<"faint");
if( cin.fail() )return false;
if( K > 2*n ) K = 2*n;
for( i=0; i<n; i++ )
{
cin >> value[i];
e[i].clear();
}
for( i=0; i<n-1; i++ )
{
cin >> a >> b;
e[a-1].push_back( b-1 );
e[b-1].push_back( a-1 );
}
return true;
}
void doit()
{
int answer = 0;
calculate( 0, K, -1);
cout << gone[0][K] << endl;
}
int main()
{
while( init() )
{
doit();
}
return 0;
}