hdu1011

/*比较苦逼的树形DP,慢慢来吧！不着急*/ #include <iostream> #include <vector> using namespace std; const int SIZE = 105;

int roomNumber, trooperNumber; int cost[SIZE], brain[SIZE]; int dp[SIZE][SIZE]; /*dp[u][p]表示用 P 个士兵占领以 u 为根节点的子树所能获得的概率最大值*/ vector<int> adj[SIZE]; /*图*/

void dfsPulsDp(int p, int pre) { for (int i = cost[p]; i <= trooperNumber; ++i) /*初始化,首先将dp[p][i]里面填充进brain[p],后面可以更新dp[p][i]的值*/ dp[p][i] = brain[p]; /*也就是说当我们有cost[p]名队员以至于更多时,我们最少可以获得brain[p]个大脑*/ int num = adj[p].size(); /*num指p节点含有的支路数*/ for (int i = 0; i < num; ++i) /*一条支路一条支路遍历,也就是所谓的dfs*/ { int v = adj[p][i]; if (v == pre) continue; /*避免死循环,节点如果是根部,就继续*/ dfsPulsDp (v, p); /*递归解决问题,先将子节点的所能得到的最大值计算出来*/

for (int j = trooperNumber; j >= cost[p]; --j) /*当队员人数一定时*/ for (int k = 1; k <= j - cost[p]; ++k) /*由于p节点一定要通过,所以一定要花费cost[p]*/ if (dp[p][j] < dp[p][j - k] + dp[v][k]) {/*v节点就两种状态,要么选择，要么不选择,选择的话dp[p][j] = dp[p][j - k] + dp[v][k],不选择的话就不变*/ dp[p][j] = dp[p][j - k] + dp[v][k]; } } }

int main() { while ((cin >> roomNumber >> trooperNumber) && (roomNumber != -1) && (trooperNumber != -1)) { int bug, bi1, bi2; int i; for (i = 0; i < roomNumber; i++) { cin >> bug >> brain[i]; cost[i] = (bug + 19) / 20; } for (i = 0; i < roomNumber; i++) adj[i].clear();

for (i = 0; i < roomNumber - 1; i++) { cin >> bi1 >> bi2; adj[bi1 - 1].push_back(bi2 - 1); adj[bi2 - 1].push_back(bi1 - 1); }

if (trooperNumber == 0) { cout << '0' << endl; continue; }

memset(dp, 0, sizeof(dp)); dfsPulsDp(0, -1); cout << dp[0][trooperNumber] << endl; } return 0; }