HDU - 1011 Starship Troopers（树形背包DP）
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N = 110;
int n,m;
vector<int> g[N];
int dp[N][N],num[N],val[N];
void dfs(int u,int fa)
{
int ww=(num[u]+19)/20;for(int i=ww;i<=m;i++) dp[u][i]=val[u];for(auto &j:g[u]){
if(j==fa) continue;dfs(j,u);for(int i=m;i>=ww;i--)for(int k=1;k<=i-ww;k++)dp[u][i]=max(dp[u][i],dp[u][i-k]+dp[j][k]);}
}
int main()
{
while(cin>>n>>m){
if(n==-1&&m==-1) break;memset(dp,0,sizeof dp);for(int i=0;i<=n;i++) g[i].clear();for(int i=1;i<=n;i++) cin>>num[i]>>val[i];for(int i=1;i<=n-1;i++){
int a,b;cin>>a>>b;g[a].push_back(b);g[b].push_back(a);}if(m==0){
cout<<"0"<<endl;continue;}dfs(1,-1);cout<<dp[1][m]<<endl;}return 0;
}