记录编号	268660	评测结果	AAAAA
题目名称	[HZOI 2016] 搜城探宝	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-06-12 17:19:44	内存使用	0.30 MiB

#include<cstdio>
using namespace std;
int f[33][33],maxl;
int n,k,shu,u,v,first[33],l[33],r[33],w[33];
bool p[33];
struct qianqu
{
    int lnum,rnum;
}last[33][33];
struct bian
{
    int v,next;
}o[111];
void add(int u,int v)
{
     o[++shu].v=v;
     o[shu].next=first[u];
     first[u]=shu;
}
void dfs1(int x)
{
    p[x]=1;
    for(int i=first[x];i;i=o[i].next)
        if(!p[o[i].v])
            if(!l[x])
            {
                l[x]=o[i].v;
                dfs1(l[x]);
            }
            else
            {
                r[x]=o[i].v;
                dfs1(r[x]);
            }
}
void dfs(int x)
{
    f[x][1]=w[x];
    if(!l[x]&&!r[x])
        return;
    if(l[x])
        dfs(l[x]);
    if(r[x])
        dfs(r[x]);
    if(l[x])
        for(int i=2;i<=k;++i)
            if(f[x][i]<w[x]+f[l[x]][i-1])
            {
                 f[x][i]=w[x]+f[l[x]][i-1];
                 last[x][i].lnum=i-1;
                 last[x][i].rnum=0;
            }
    if(r[x])
        for(int i=2;i<=k;++i)
            if(f[x][i]<f[r[x]][i-1]+w[x])
            {
                 f[x][i]=f[r[x]][i-1]+w[x];
                 last[x][i].rnum=i-1;
                 last[x][i].lnum=0;
            }
    if(l[x]&&r[x])
        for(int i=3;i<=k;++i)
            for(int j=1;j<=i-2;++j)
                if(f[x][i]<f[l[x]][j]+f[r[x]][i-j-1]+w[x])
                {
                     f[x][i]=f[l[x]][j]+f[r[x]][i-j-1]+w[x];
                     last[x][i].lnum=j;
                     last[x][i].rnum=i-j-1;
                }
}
void digui(int x,int num)
{
    p[x]=0;
    if(!last[x][num].lnum&&!last[x][num].rnum)
        return;
    if(last[x][num].lnum)
        digui(l[x],last[x][num].lnum);
    if(last[x][num].rnum)
        digui(r[x],last[x][num].rnum);
}
int main()
{
	freopen("hzoi_key.in","r",stdin);
	freopen("hzoi_key.out","w",stdout);
    scanf("%d%d",&n,&k);
    ++k;
    for(int i=1;i<n;++i)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;++i)
        scanf("%d",&w[i]);
    dfs1(1);
    dfs(1);
    --k;
    if(n==k)
    {
        printf("%d",f[1][k]);
        return 0;
    }
    for(int i=1;i<=n;++i)
        if(f[i][k+1]>maxl)
            maxl=f[i][k+1];
    for(int i=1;i<=k;++i)
    {
        for(int j=0;j<33;++j)
            p[j]=1;
        digui(1,i);
        for(int j=1;j<=n;++j)
            if(p[j]&&f[1][i]+f[j][k-i+1]>maxl)
                maxl=f[1][i]+f[j][k-i+1];
    }
    printf("%d",maxl);
}