记录编号	189970	评测结果	ATTTTTAATT
题目名称	通往自由的钥匙	最终得分	30
用户昵称	devil	是否通过	未通过
代码语言	C++	运行时间	7.125 s
提交时间	2015-09-30 22:14:15	内存使用	0.36 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=110;
const int maxm=3000;
//const int mod=10007;

struct node
{
    int l,r;
    int c,v;
    node() {l=r=-1;c=v=0;}
} tree[maxn];

vector<int> G[maxn];
int vis[maxn];
int f[maxn][maxn];

void build_tree(int root)
{
    vis[root]=1;
    int len=G[root].size();
    for(int i=0;i<len;i++)
    {
        int v=G[root][i];
        if(!vis[v])
        {
            if(tree[root].l==-1) tree[root].l=v;
            else tree[v].r=tree[root].l,tree[root].l=v;
            build_tree(v);
        }
    }
}

int dp(int u,int p)
{
    if(u==-1) return 0;
    //if(f[u][p]>0) return f[u][p];
    int temp=0;
    for(int i=0;i<=p-tree[u].c;i++)
    {
        temp=max(temp,dp(tree[u].l,i)+
                dp(tree[u].r,p-tree[u].c-i));
    }
    int t2=dp(tree[u].r,p);
    if(p-tree[u].c<0) return f[u][p]=max(f[u][p],t2);
    return f[u][p]=max(temp+tree[u].v,t2);
}

int main()
{
    freopen("key.in","r",stdin);
    freopen("key.out","w",stdout);
    //clock_t st=clock();
    int n,p;scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&tree[i].c,&tree[i].v);
        f[i][tree[i].c]=tree[i].v;
    }
    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    build_tree(1);tree[0].l=1;
    //for(int i=1;i<=n;i++) printf("%d %d\n",tree[i].l,tree[i].r);
    printf("%d\n",dp(0,p));
    /*for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=p;j++)
        {
            printf("%d ",f[i][j]);
        }
        printf("\n");
    }*/
    //clock_t ed=clock();
    //printf("\nTime used : %.7lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}