题目（BZOJ）
这题其实很好做.....
亏我一开始把网络流建图给想出来了233
然后又去思考了一下树剖，LCT，dfs序啥的...
发现这题根本不需要这么麻烦，只需要做一次长链树剖（每次沿链最长的点，平常的树剖是沿子树大小最大的点）就行了，因为剖下来的每条链的末尾一定是叶子结点并且不会出现重叠情况，所以将每条链的总权值从大到小排序，选前k个就行了（我用的vector）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
e=0;bool ck=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
if(ck)e=-e;
}
const int N=200050;
int n,k;ll a[N];
struct edge{
int vk,nxt;
}e[N<<1];
int tt,head[N];
inline void ad(int u,int v){e[++tt].vk=v;e[tt].nxt=head[u];head[u]=tt;}
int f[N],son[N];ll siz[N];
vector <ll> vec;
inline bool cmp(const ll &x,const ll &y){
return x>y;
}
void dfs1(int u,int fa){
siz[u]=a[u];f[u]=fa;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].vk;
if(v==fa)continue;
dfs1(v,u);
siz[u]=max(siz[u],siz[v]+a[u]);
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
void dfs2(int u,int fa,ll sz){
if(!son[u]){
vec.push_back(sz);
return;
}
dfs2(son[u],fa,sz+a[son[u]]);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].vk;
if(v==son[u]||v==f[u])continue;
dfs2(v,v,a[v]);
}
}
int main(){
read(n),read(k);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<n;++i){
int x,y;read(x),read(y);
ad(x,y),ad(y,x);
}
dfs1(1,0);
dfs2(1,1,a[1]);
sort(vec.begin(),vec.end(),cmp);
ll ans=0;
for(int i=0;i<k;++i)ans+=vec[i];
printf(
return 0;
}