题目大意：很简单了，不再赘述。
做法一：
首先我们很明显可以考虑到一个贪心策略，我们每次选择目前最大的一条链进行选择，然后删掉这条链，重复 k 次就是结果。
我们先假设这个策略是正确的，那么我们只需要每次贪心选出来目前的最大值。这个稍微手玩一下可以知道是一个带权的长链剖分，或者也可以用可并堆或者其他很多种方法维护，其他题解也给出了实现方法，这里就不再放代码了。
给出以下这种做法的证明：
首先很明显观察到，我们如果选完了若干个路径后，剩下的点一定会组成一个森林。
考虑我们目前选了 1\rightarrow p 这一条路径，如果我们考虑不选择这条边，其他的任意策略选择，并且有更优的方案。我们考虑对于没有选 1\rightarrow p 这条路径时的森林。
-
如果 p 所在的这颗树在更优的方案中并没有选择，那么我们可以随便删掉后面的一条路径并且加入这条路径，因为这条路径是当前最优的，后面的还会有覆盖，权值也不优，所以矛盾了。
-
如果有选择，那么我们考虑找到 p\rightarrow 1 这条路径上第一个在更优的方案里在路径上的点，并且在另一种方案里过这个点的路径是 q\rightarrow 1，那么我们换成 1\rightarrow p 一定更优，因为重合的部分一样，下面的两条链中，1\rightarrow p 一定不被覆盖并且权值更大，所以更优。
所以我们证明了这个策略是对的。
做法二：
我们可以考虑一个费用流的模型，进行如下建边：
儿子对父亲连边，一共两种，一种流量为 $1$，费用为 $a_u$，$u$ 是儿子；另一种流量为 $\infty$，费用为 $0$。我们这里令根节点的父亲为 $T$。
很显然，推 $k$ 个流进去求最大费用最大流就是答案，因为我们肯定优先走有权边。
然后我们考虑模拟费用流，维护当前增广的最大值。
首先我们先考察一下一次增广路可能的形状，发现其实都是从叶子节点到根这样的一条增广路，因为你走反边再走上去是很没有意义的，这样只会让增广路更小。
然后我们考虑一次增广后对其他节点权值的影响，或者我们其实可以只考虑那些有权边删除时的影响，因为 0 权的跑了无所谓，总可以有足够的 0 权边。
然后我们发现，有权边只有 $n$ 条，所以我们可以暴力删除，那就转化为删除一条有权边之后的影响。这个其实很显然，就是对整个子树的权值做一次减法就可以完成修改。
那么我们现在要求这样一个东西：
- 子树加法。
- 全局询问最大值和出现位置。
很显然可以用线段树维护，直接按照 dfn 序拍成序列就可以做完了，复杂度 $O(n\log n)$。
其实这么做完发现本质其实是一样的，所以其实也可以直接用下面这种做法给出一种上面做法的一种另类的证明。
给出代码：
```
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 5;
int n, k, a[maxn], use[maxn], tot, dfn[maxn], sz[maxn], f[maxn];
vector<int> e[maxn];
struct node {
int mx, p;
friend node operator+(node x, node y) {
return (x.mx < y.mx ? y : x);
}
};
struct Segtree {
node tr[maxn << 2];
int tag[maxn << 2];
void pushup(int t) {
tr[t] = tr[t << 1] + tr[t << 1 | 1];
}
void addtag(int t, int val) {
tr[t].mx += val, tag[t] += val;
}
void pushdown(int t) {
addtag(t << 1, tag[t]);
addtag(t << 1 | 1, tag[t]);
tag[t] = 0;
}
void update(int l, int r, int x, int y, int t, int val) {
if(x <= l && r <= y) {
addtag(t, val);
return ;
}
int mid = l + r >> 1;
pushdown(t);
if(x <= mid)
update(l, mid, x, y, t << 1, val);
if(mid < y)
update(mid + 1, r, x, y, t << 1 | 1, val);
pushup(t);
}
void modify(int l, int r, int pos, int t, int val) {
if(l == r) {
tr[t].p = val;
return ;
}
int mid = l + r >> 1;
if(pos <= mid)
modify(l, mid, pos, t << 1, val);
else
modify(mid + 1, r, pos, t << 1 | 1, val);
pushup(t);
}
} tree;
void dfs(int u, int fa) {
sz[u] = 1, dfn[u] = ++tot;
f[u] = fa;
tree.modify(1, n, dfn[u], 1, u);
for (int i = 0; i < e[u].size(); i++) {
int v = e[u][i];
if(v == fa)
continue;
dfs(v, u);
sz[u] += sz[v];
}
tree.update(1, n, dfn[u], dfn[u] + sz[u] - 1, 1, a[u]);
}
void upd(int x) {
if(use[x] || !x)
return ;
use[x] = 1;
tree.update(1, n, dfn[x], dfn[x] + sz[x] - 1, 1, -a[x]);
upd(f[x]);
}
signed main() {
cin >> n >> k;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
dfs(1, 0);
int ans = 0;
for (int i = 1; i <= k; i++) {
node tmp = tree.tr[1];
ans += tmp.mx;
upd(tmp.p);
}
cout << ans << endl;
return 0;
}
```