[bzoj3252]-[SCOI2017]攻略

真没想到去年SCOI出原题…..

(所以标题我自己加了个SCOI2017上去233)


题目(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("%lld",ans);
    return 0;
}