传送门
长链剖分好题。
题意：给一棵带点权的树，可以从根节点到任一叶节点走kkk次，走过的点只能计算一次，问kkk次走过的点点权值和最大值。
思路：
考虑将整棵树带权长链剖分，这样链与链之间是不会重复选择的。
然后每条链都对应一种方案，我们贪心选择前kkk大即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
typedef long long ll;
const int N=2e5+5;
int n,k,a[N],fa[N],hson[N],top[N],len[N];
ll ans=0,dep[N],mxdep[N];
vector<int>e[N];
vector<ll>sum;
void dfs1(int p){
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=mxdep[v]=dep[p]+a[v],dfs1(v),mxdep[p]=max(mxdep[v],mxdep[p]);
if(mxdep[v]==mxdep[p])hson[p]=v;
}
}
void dfs2(int p,int tp,ll all){
top[p]=tp;
if(hson[p])dfs2(hson[p],tp,all+a[hson[p]]);
else{sum.push_back(all);return;}
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v,a[v]);
}
int main(){
n=read(),k=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),dfs2(1,1,a[1]),sort(sum.begin(),sum.end());
for(ri i=sum.size()-1,tim=k;~i&&tim;--tim,--i)ans+=sum[i];
cout<<ans;
return 0;
}