P10641 BZOJ3252 攻略 题解

· · 题解

题目传送门

Solution

长链剖分大佬们都将的很清楚了，我就来补一发左偏树吧。

我们可以每个节点建一个大根堆，然后自底向上合并。

因为每个节点对答案的贡献最多只有一次，我们可以 dfs 一遍，把 x 的子树合并完后，将 x 的权值加到左偏树的堆顶元素上即可。

其实就是将每一层的最大元素连成一条链。

最后的左偏树中取前 k 大求和即为解。

比如这棵树（样例），k=2：

我们先将最底层的 3 和 4 合并，得到堆护的序列 2,1。

然后将 2 的权值加到堆顶元素上，序列变为 5,1。

再将 2 和 5 合并，得到序列 5,1,1。

最后将 1 的权值加到堆顶元素上，序列变为 9,1,1。

取前 2 个元素求和就可以得到答案 10。

其中 9 表示 1,2,3 这条链，1 表示 5 或 4 这条链。

Code(100 pts):

#include<bits/stdc++.h>
#define afor(x,y,z) for(int x=y;x<=z;x++)
#define bfor(x,y,z) for(int x=y;x>=z;x--)
#define cfor(x,y) for(int x=head[y];x;x=nxt[x])
using namespace std;
typedef long long ll;
typedef const int cint;
cint N=2e5+10;
ll n,k,rt,ans,v[N],w[N],d[N],lson[N],rson[N];
ll tot,head[N],to[N],nxt[N];
void add(ll x,ll y) {
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
ll merge(ll x,ll y) {
    if(!x||!y) return x+y;
    if(w[x]<w[y]) swap(x,y);
    rson[x]=merge(rson[x],y);
    if(d[lson[x]]<d[rson[x]])
        swap(lson[x],rson[x]);
    d[x]=d[rson[x]]+1;
    return x;
}
ll dfs(ll x) {
    ll ret=0;
    cfor(i,x) {
        ll y=dfs(to[i]);
        if(y) ret=merge(ret,y);
        else ret=merge(ret,to[i]);
    }
    if(ret) w[ret]+=w[x];
    return ret;
}
int main() {
    scanf("%lld%lld",&n,&k);
    afor(i,1,n) scanf("%lld",&w[i]);
    afor(i,1,n-1) {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        add(x,y),v[y]=1;
    }
    afor(i,1,n) if(!v[i]) rt=i;
    ll heap=dfs(rt);
    afor(i,1,k) {
        ans+=w[heap];
        heap=merge(lson[heap],rson[heap]);
    }
    printf("%lld",ans);
    return 0;
}