#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 100+5 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; int head[MAXN],vis[MAXN],ptr=1; int dp[MAXN][MAXN],tmp[MAXN],bug[MAXN],val[MAXN]; struct node{int y,next,val;}tree[MAXN<<2]; void init() { mem(head,-1); mem(vis,0); ptr = 1; } void add(int son,int fa) { tree[ptr].y=son; tree[ptr].next=head[fa]; head[fa]=ptr++; } void dfs(int rt) { vis[rt] = 1; //if(head[rt]==-1 && bug[rt]==0) bug[rt] = 1; int v1 = (bug[rt]+19)/20; for(int i=v1;i<=m;i++) dp[rt][i] = val[rt]; for(int i=head[rt];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(y); for(int j=m;j>=v1;j--) { for(int k=1;j-k>=v1;k++) { dp[rt][j] = max(dp[rt][j],dp[rt][j-k]+dp[y][k]); } } } } int main() { int i,j,k=1; while(~sf("%d%d",&n,&m)) { if(m==-1 && n==-1) break; init(); for(i=1;i<=n;i++) { sf("%d%d",&bug[i],&val[i]); } for(i=1;i<n;i++) { int x,y; sf("%d%d",&x,&y); add(x,y); add(y,x); } dfs(1); pf("%d\n",dp[1][m]); } }
原文:http://www.cnblogs.com/qlky/p/5808721.html