【题意说明】
一棵树有n个结点，n-1条边，每个结点有个权值。每次可以获得从根节点走到叶子结点所有结点的权值和，但是每个结点的权值只能使用一次。求走k次所能获得的最大权值和。
【问题分析】
dfs1求出所有所有点重儿子（以权值和大小划分），dfs2保留每条重链（top点）的权值和，其它的点全部清为-1。
然后再每个点的权值从大到小排个序，取前面的k个。
显然每条重链都会到叶子结点。而且所取的K条重链也都可以走到（即前K个依次取，都能按题意要求从1开始到达每条重链的叶子结点）。
【参考代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define to(i) edge[i].to
#define nx(i) edge[i].next
#define sz(i) sum[i]
#define hd(i) node[i].head
#define vl(i) node[i].value
#define sn(i) node[i].son
#define tp(i) node[i].top
#define id(i) node[i].index
#define ll long long
const int maxN=100010;
struct Edge{
int to, next;
}edge[maxN];
struct Node{
int head, value, son, top, index;
}node[maxN];
ll sum[maxN];
int n, k, t;
void init();
void work(int);
void dfs1(int);
void dfs2(int, int);
void addedge(int, int, int);
int main(){
scanf("%d", &t);
for(int i=0; i<t; i++){
init();
work(i+1);
}
return 0;
}
void init(){
memset(sum, 0, sizeof(sum));
memset(node, 0, sizeof(node));
memset(edge, 0, sizeof(edge));
scanf("%d%d", &n,
&k);
for(int i=1; i<=n; i++)
scanf("%d", &vl(i));
for(int i=1; i<n; i++){
int x, y;
scanf("%d%d",
&x, &y);
addedge(x, y, i);
}
dfs1(1);
dfs2(1, 1);
}
void addedge(int x, int y, int k){
to(k)=y; nx(k)=hd(x); hd(x)=k;
}
void dfs1(int k){
sz(k)=vl(k);
for(int i=hd(k); i; i=nx(i)){
if(sz(to(i))) return;
dfs1(to(i));
if(sz(sn(k))<sz(to(i)))
sn(k)=to(i);
sz(k)=sz(sn(k))+vl(k);
}
}
void dfs2(int k, int _tp){
id(k)=1;
if(k!=_tp) sz(k)=0;
if(sn(k)) dfs2(sn(k), _tp);
for(int i=hd(k); i; i=nx(i))
if(!id(to(i))) dfs2(to(i),
to(i));
}
void work(int t){
sort(sum+1, sum+n+1);
int i=n; ll total=0;
while(k&&sz(i)>0){
total+=sz(i);
i--; k--;
}
printf("Case #%d:
%I64d
", t, total);
}