bzoj3090: Coci2009 [podjela]

这个范围明显树包的

然而值并不滋磁

想了一会发现可以带一维当前子树用了多少边，搞定当前向上还能送多少

然后发现会有搞不定的情况，要向上传负数

每次都要重新初始化，负数强制要要

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int maxn=;

struct node

{

    int x,y,next;

}a[maxn*];int len,last[maxn];

void ins(int x,int y)

{

    len++;

    a[len].x=x;a[len].y=y;

    a[len].next=last[x];last[x]=len;

}

int f[maxn][maxn],c[maxn],li[maxn];

void dfs(int x,int fr)

{

    f[x][]=c[x];

    li[x]=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(y!=fr)

        {

            dfs(y,x);

            li[x]+=li[y]+;

            for(int i=li[x];i>=;i--)

            {

                int d=f[][];

                for(int j=min(i,li[y]);j>=;j--)

                {

                    if(f[x][i-j]!=f[][]&&f[y][j]!=f[][]&&f[y][j]>=)

                        d=max(d,f[x][i-j]);

                    if(i!=j&&f[x][i-j-]!=f[][]&&f[y][j]!=f[][])

                        d=max(d,f[x][i-j-]+f[y][j]);

                }

                f[x][i]=d;

            }

        }

    }

}

int main()

{

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    int n,X;

    scanf("%d%d",&n,&X);

    for(int i=;i<=n;i++)

        scanf("%d",&c[i]),c[i]=X-c[i];

    int x,y; len=;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&x,&y);

        ins(x,y),ins(y,x);

    }

    memset(f,-,sizeof(f));

    dfs(,);

    for(int i=;i<n;i++)

        if(f[][i]>=){printf("%d\n",i);break;}

    return ;

}