奋战杭电ACM（DAY9）1011

#include<iostream>
using namespace std;const int MAXN=110;
int N,M;struct Node
{int number,p;//p:该结点的possible；number：该结点的bug数
};
Node node[MAXN];//记录结点 int dp[MAXN][MAXN];//DP，dp[i][j]表示跟结点为i时，用掉j个士兵获得的最大值 
int adj[MAXN][MAXN];//存树 。adj[i][j]：结点为i，adj[i][0]表示该结点所连接的结点（父结点和子结点一共）个数//adj[i][j]（j>=1）表示结点编号，j=结点个数+1
bool vis[MAXN];//访问标记 int max(int a, int b)
{return a>b ? a:b;
}void dfs(int root)//DFS，求该结点及其分支所能获得的最大possible
{vis[root]=true;//已经访问 int num=(node[root].number+19)/20;//获得该结点需要的士兵数目 for(int i=num;i<=M;i++)  dp[root][i]=node[root].p;//用掉i个士兵获得的possiblefor(i=1;i<=adj[root][0];i++){int u=adj[root][i];if(vis[u]) continue;//跳过已访问的，包括该结点的父节点和子结点dfs(u);//求该子结点的最大possiblefor(int j=M;j>=num;j--){for(int k=1;j+k<=M;k++)//剩余的士兵{if(dp[u][k])//该子结点的最大possibledp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[u][k]);//j+k：父节点和子结点共用了士兵数目//dp[root][j+k]父结点和前i-1个子结点中所获possible的最大值//dp[root][j]+dp[u][k]父结点和当前子结点u一共所获possible//用来找出所有子结点里能得到的最大possible//即该父结点能得到的最大possible}    }    }    
}  int main()
{int b,e;while(cin >> N >> M){if(N==-1&&M==-1) break;memset(vis,false,sizeof(vis));memset(dp,0,sizeof(dp));memset(adj,0,sizeof(adj));for(int i=1;i<=N;i++)cin >> node[i].number >>node[i].p;for(i=1;i<N;i++)//存图 {cin >> b >> e;//连接结点b和eadj[b][0]++;adj[b][adj[b][0]]=e;adj[e][0]++;adj[e][adj[e][0]]=b;}if(M==0)//这个必需要，有代价为0的房间，M=0则无法获得 cout << 0 << endl;else{dfs(1);cout << dp[1][M] << endl;}    } return 0;   
}