Description
题目简述：树版[k取方格数]
众所周知，桂木桂马是攻略之神，开启攻略之神模式后，他可以同时攻略k部游戏。今天他得到了一款新游戏《XX
半岛》，这款游戏有n个场景(scene)，某些场景可以通过不同的选择支到达其他场景。所有场景和选择支构成树状
结构：开始游戏时在根节点（共通线），叶子节点为结局。每个场景有一个价值，现在桂马开启攻略之神模式，同
时攻略k次该游戏，问他观赏到的场景的价值和最大是多少（同一场景观看多次是不能重复得到价值的）
“为什么你还没玩就知道每个场景的价值呢？”
“我已经看到结局了。”
Input
第一行两个正整数n,k
第二行n个正整数，表示每个场景的价值
以下n-1行,每行2个整数a,b，表示a场景有个选择支通向b场景（即a是b的父亲）
保证场景1为根节点
n<=200000，1<=场景价值<=2^31-1
Output
输出一个整数表示答案
Sample Input
5 2
4 3 2 1 1
1 2
1 5
2 3
2 4
Sample Output
10
Solution
考虑贪心，我们需要找满足以下条件的 (k) 条路径：
路径与路径之间没有重叠（以不重复计算贡献）；每条路径的终点一定是叶子；每条路径要可以直接或间接地到达根（即通过其它路径）
然后答案要最大，那么就是要找权值和最大的 (k) 条路径
会发现，这些东西极其地类似于长链剖分。我们如果按照权值进行长链剖分，可以最优地将树分割成满足条件的一个个路径，取最大的 (k) 个即可
大概证明一下，首先长链剖分，每条链都是到达叶子节点的，并且肯定不会重复；然后因为是按照权值来剖分的，所以如果最终我们选了一个起点不是根的链，那么它的的起点的父亲所在的链一定被选了，因为它们是重链和轻链的关系
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
#define REP(a,b,c) for(register int a=b,a##end=c;a<=a##end;++a)
#define DEP(a,b,c) for(register int a=b,a##end=c;a>=a##end;--a)
const int MAXN=200000+10;
int n,k,e,beg[MAXN],nex[MAXN],to[MAXN],val[MAXN],top[MAXN],hson[MAXN];
ll sum[MAXN],Mx[MAXN],ans;
std::priority_queue<ll> q;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void dfs1(int x,int f)
{
hson[x]=x;sum[x]=sum[f]+val[x];
for(register int i=beg[x];i;i=nex[i])
{
dfs1(to[i],x);
if(Mx[to[i]]>Mx[x])Mx[x]=Mx[to[i]],hson[x]=to[i];
}
Mx[x]+=val[x];
}
inline void dfs2(int x,int tp)
{
top[x]=tp;
if(hson[x]!=x)dfs2(hson[x],tp);
for(register int i=beg[x];i;i=nex[i])
if(to[i]==hson[x])continue;
else dfs2(to[i],to[i]);
}
inline void dfs(int x)
{
int ch=0;
for(register int i=beg[x];i;i=nex[i])dfs(to[i]),ch++;
if(!ch)q.push(sum[x]-sum[top[x]]+val[top[x]]);
}
int main()
{
read(n);read(k);
REP(i,1,n)read(val[i]);
REP(i,1,n-1)
{
int u,v;read(u);read(v);
insert(u,v);
}
dfs1(1,0);dfs2(1,1);dfs(1);
while(!q.empty()&&k--)ans+=q.top(),q.pop();
write(ans,'
');
return 0;
}