传送门

不知道扯啥了，就想构造个密码，然而搜狗打不出来“横折弯”，百度上也没搜出来。。。

所以这不就有的扯了吗

考虑一个贪心：每次取权值最大的路径，然后把这条路径上的点权清空。

不会理性证明，那就感性理解一下，看起来挺对的。

用不大一样的长剖优化。不以深度划分长短儿子，而是以权值和划分，然后把所有长链扔到堆里取前$k$大。

正确性的话，根据上面的贪心，某个点一定是被它下面最大的一条路径取走。这若干条不相交的链就可以代表取走每个叶子时的权值。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

#define maxn 200005
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
priority_queue<long long>q;
long long md[maxn];
int son[maxn],a[maxn],top[maxn],h[maxn],num;
struct edge{int pre,to;}e[maxn];
inline void add(int from,int to){e[++num]=(edge){h[from],to},h[from]=num;}
void dfs1(int node=1){
    md[node]=a[node];
    for(register int i=h[node],x;i;i=e[i].pre){
        x=e[i].to,dfs1(x);
        if(md[x]>md[son[node]])son[node]=x,md[node]=md[x]+a[node];
    }
}
void dfs2(int node=1){
    if(top[node]==node)q.push(md[node]);
    if(!son[node])return;
    top[son[node]]=top[node],dfs2(son[node]);
    for(register int i=h[node],x;i;i=e[i].pre){
        x=e[i].to;
        if(x!=son[node])top[x]=x,dfs2(x);
    }
}
int main(){
    top[1]=1;
    int n=read(),k=read();
    long long ans=0;
    for(register int i=1;i<=n;++i)a[i]=read();
    for(register int i=1,x;i<n;++i)x=read(),add(x,read());
    dfs1(),dfs2();
    while(k--)ans+=q.top(),q.pop();
    printf("%lld\n",ans);
}