\(\text{Solution:}\)
题目是指每次选择一条链就会把它清空，求选 \(k\) 条链的最大价值。
打眼看上去不知道咋做……想一下这不就是个长链剖分！
维护一个带权的长链剖分，然后直接对每一条链的权值和排序，取前 \(k\) 大就可以了。
因为长链剖分的每一条链都是不重复的，没有公共部分，恰好对应了删掉之后的链；由于我们按照权值做的带权长剖，所以它也满足贪心的性质。
这样就直接用长链剖分把贪心优化掉了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=2e5+10;
int head[MAXN],tot,n,top[MAXN];
int len[MAXN],son[MAXN],pa[MAXN];
int val[MAXN],k;
vector<int>vec;
struct E{int nxt,to;}e[MAXN<<1];
inline void add(int x,int y){e[++tot]=(E){head[x],y};head[x]=tot;}
void dfs1(int x,int fa){
pa[x]=fa;
for(int i=head[x];i;i=e[i].nxt){
int j=e[i].to;
if(j==fa)continue;
dfs1(j,x);
if(len[j]>len[son[x]])son[x]=j;
}
len[x]=len[son[x]]+val[x];
}
void dfs2(int u,int t){
top[u]=t;
if(son[u])dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int j=e[i].to;
if(j==pa[u]||j==son[u])continue;
dfs2(j,j);
}
}
signed main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;++i)scanf("%lld",&val[i]);
for(int i=1;i<n;++i){
int u,v;
scanf("%lld%lld",&u,&v);
add(u,v);add(v,u);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=n;++i)if(top[i]==i)vec.push_back(-len[i]);
// for(int i=1;i<=n;++i)printf("%d ",len[i]);
// cout<<endl;
sort(vec.begin(),vec.end());
int ans=0;
for(int i=0;i<k;++i)ans-=vec[i];
cout<<ans<<endl;
return 0;
}