HiHo一下 Week12 刷油漆

HiHo

描述

上回说到，小Ho有着一棵灰常好玩的树玩具！这棵树玩具是由N个小球和N-1根木棍拼凑而成，这N个小球都被小Ho标上了不同的数字，并且这些数字都是处于1..N的范围之内，每根木棍都连接着两个不同的小球，并且保证任意两个小球间都不存在两条不同的路径可以互相到达。没错，这次说的还是这棵树玩具的故事！
小Ho的树玩具的质量似乎不是很好，短短玩了几个星期，便掉漆了！
“简直是一场噩梦！”小Ho拿着树玩具眼含热泪道。
“这有什么好忧伤的，自己买点油漆刷一刷不就行了？”小Hi表示不能理解。
“还可以这样？”小Ho顿时兴高采烈了起来，立马跑出去买回来了油漆，但是小Ho身上的钱却不够——于是他只买回了有限的油漆，这些油漆最多能给M个结点涂上颜色，这就意味着小Ho不能够将他心爱的树玩具中的每一个结点都涂上油漆！
小Ho低头思索了半天——他既不想只选一部分结点补漆，也不想找小Hi借钱，但是很快，他想出了一个非常棒的主意：将包含1号结点的一部分连通的结点进行涂漆（这里的连通指的是这一些涂漆的结点可以互相到达并且不会经过没有涂漆的结点），然后将剩下的结点拆掉！
那么究竟选择哪些结点进行涂漆呢？小Ho想了想给每个结点都评上了分——他希望最后留下来，也就是涂漆了的那些结点的评分之和可以尽可能的高！
那么，小Ho该如何做呢？

输入

每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第一行为两个整数N、M，意义如前文所述。
每组测试数据的第二行为N个整数，其中第i个整数Vi表示标号为i的结点的评分
每组测试数据的第3~N+1行，每行分别描述一根木棍，其中第i+1行为两个整数Ai，Bi，表示第i根木棍连接的两个小球的编号。
对于100%的数据，满足N<=10^2，1<=Ai<=N, 1<=Bi<=N, 1<=Vi<=10^3, 1<=M<=N
小Hi的Tip：那些用数组存储树边的记得要开两倍大小哦！

输出

对于每组测试数据，输出一个整数Ans，表示使得涂漆结点的评分之和最高可能是多少。

样例

样例输入

10 4
370 328 750 930 604 732 159 167 945 210 
1 2
2 3
1 4
1 5
4 6
4 7
4 8
6 9
5 10

样例输出
2977

思路

这道题的数据结构和上一道题明显是一样的。(’ｰ’)
ans[i][j]表示以i为根节点，包括m个的节点的联通分量能获得最大的value。
那么这道题目就是要求ans[1][m]。
然后就可以用动态规划来处理啦，和背包问题有些类似。
动态规划方程为：
$ans[i,j]=max(ans[i,j],ans[i,j-x]+ans[i\_child,x])$
其中i_child为i的子节点，x为1~m-1的值。
在循环中要注意为什么下面代码里的t是从m开始递减循环。如果从2到m循环的话，同一个子节点可能会被加入多次，就像完全(无限)背包问题一样，而这里情况和01背包更为相像，也就是一件物品只能被选择一次。

代码

#include<iostream>
using namespace std;
int n,m;
int value[102];
int ans[102][102]={0};
int h[102]={0};
int p=1;
struct tree_node{
    int next;
    int to;
}node[204];
int max(int a,int b){
    if(a>b) return a;
    else return b;
}
int ergodic(int point,int former){
    if(h[point]==0||node[h[point]].to==former) {
        for (int b=1;b<=m;b++) ans[point][b] = value[point];
        return value[point];
    }   
    ans[point][1]=value[point];
    int i=h[point];
    while(node[i].to){
        if(node[i].to!=former){
            ergodic(node[i].to,point);
            for(int t=m;t>=2;t--){
                for(int kk=1;kk<=t-1;kk++)
                ans[point][t]=max(ans[point][t],ans[point][t-kk]+ans[node[i].to][kk]);
            }
        }
        i = node[i].next;
    }
}
void build(int from,int to){
    node[p].to = to; node[p].next = h[from];
    h[from] = p++;
    node[p].to = from; node[p].next = h[to];
    h[to]=p++;
}
int main(){
    int i,j,k;
    cin >> n >> m;
    for (i=1;i<=n;i++)cin >> value[i];
    for(i=1;i<n;i++){
        cin >> j >> k;
        build(j,k);
    }
    ergodic(1,0);
    cout << ans[1][m];
    return 0;
}