学步园

浙大的题还有有一定的难度的，看了大牛的解题报告才会~ 思路难想，假如想到了写代码是很快的事

题意：

对一棵树做恰好k次cut操作，每次可以cut一条边，然后丢掉其中一部分而得到一棵新的树。要求最后得到的树的最小和最大权值的和

分析：

比较经典的树形DP模型，其中每个节点对所有儿子又是一个二维DP。DP记录以该节点为根，cut了0 ~ k次所能得到的最小/最大权值。每次有两种选择，一种是保留child，这样update(dp[parent][a + b], dp[parent][a] + dp[child][b])。另一种是直接舍去这棵子树，这样update(dp[parent][a
+ b], dp[parent][a])，其中b可以取1 ~ sizeOfSubtree(j)，而不仅仅是1。最后的答案包括两种情况，一种是根在最优解中，那么就是dp[root][k]。否则假设i是最优解中离根最近的点，那么最优解是dp[i][k - j]，其中j可以取1 ~ (n – sizeOfSubtree(i))，同样j不仅仅可以取1。

//AC CODE：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define INF 9999999
int dp[1010][22];//DP记录以该节点为根,cut了0到m次所能得到的最小或者最大权值
int d[1010];//d[i]表示i结点的出度
int num[1010];
int n,m;
int head[1010],cnt;
struct node//模拟vector stl里的太龟速了
{
    int y,next;
} a[3030];
void add(int x,int y)
{
    a[cnt].y=y;
    a[cnt].next=head[x];
    head[x]=cnt++;
}

void dfs(int x,int root)
{
    dp[x][0]=num[x];//初始化x结点
    d[x]=0;//初始化x结点
    for(int i=1; i<=m; i++)//初始化x结点
        dp[x][i]=INF;
    for(int i=head[x]; i; i=a[i].next)
    {
        if(a[i].y==root)//root是i的父节点，不能当作i结点的孩子处理
            continue;
        dfs(a[i].y,x);
        d[x]+=d[a[i].y]+1;//度数总和(出度)加上与child的这一边，所以  +1
        for(int j=m; j>=0; j--)
        {
            //1：j刀切在父结点上，直接合并child
            dp[x][j]+=dp[a[i].y][0];
            //2：保持父子关系,自己切k刀,child切j-k刀
            for(int k=0; k<j; k++)
                dp[x][j]=min(dp[x][j],dp[x][k]+dp[a[i].y][j-k]);
            //3：不要父子关系，可以切1到d[a[i].y]+1刀  父亲和孩子的边也是一刀 +1
            for(int k=1; k<=d[a[i].y]+1&&k<=j; k++)
                dp[x][j]=min(dp[x][j],dp[x][j-k]);
        }
    }
}

int cal()
{
    dfs(1,0);//从结点一开始，0为1的父节点
    int ans=dp[1][m];
    if(m>0)
    {
        for(int i=2; i<=n; i++)
            for(int j=max(0,m-d[1]+d[i]); j<=d[i]&&j<m; j++)//d[i]保存出度
            {
                ans=min(ans,dp[i][j]);
            }
    }
    return ans;
}

int main()
{
    int i,x,y;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        cnt=1;
        memset(head,0,sizeof(head));
        for(i=1; i<=n; i++)
            scanf("%d",&num[i]);
        for(i=1; i<n; i++)
        {
            scanf("%d%d",&x,&y);
            add(x,y);//图需要建立双向边
            add(y,x);
        }
        printf("%d ",cal());
        for(i=1; i<=n; i++)
            num[i]=-num[i];
        printf("%d\n",-cal());
    }
}