给定一棵树,每个点有点权,选定(k)个叶子,满足根到(k)个叶子的所有路径所覆盖的点权和最大。
首先考虑一个贪心,每一次选择权值最大的一条链,然后把这条链上的权值清零,重复(k)次
于是很显然这样的贪心可以等价于把这棵树给剖成若干条链。那么考虑用长链剖分来搞,只要把链的长度换成所有点的权值和就可以了。把所有的链的权值sort一下取前(k)大就行了
//minamoto
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int read(){
int res,f=1;char ch;
while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
return res*f;
}
const int N=5e5+5;
int head[N],Next[N<<1],ver[N<<1],tot;
inline void add(int u,int v){ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
int a[N],n,k,son[N],top;ll mx[N],st[N],ans;
void dfs1(int u){
for(int i=head[u];i;i=Next[i]){
int v=ver[i];dfs1(v);
if(mx[v]>mx[son[u]])son[u]=v;
}
mx[u]=mx[son[u]]+a[u];
}
void dfs2(int u,int tp){
if(u==tp)st[++top]=mx[u];
if(son[u])dfs2(son[u],tp);
for(int i=head[u];i;i=Next[i])
if(ver[i]!=son[u])dfs2(ver[i],ver[i]);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read(),k=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1,u,v;i<n;++i)u=read(),v=read(),add(u,v);
dfs1(1),dfs2(1,1),sort(st+1,st+1+top);
for(int i=top,j=k;i&&j;--i,--j)ans+=st[i];
printf("%lld
",ans);return 0;
}