左偏树

· · 个人记录

定义

左偏树实际上是可合并的堆。

节点不仅存了权值，还存了一个比较重要的信息 \mathrm{dis}。

#### 性质 - 根的 $\mathrm{dis}$ 不超过 $\log n$ 级别。 事实上根的 $\mathrm{dis}$ 不超过 $\left\lceil\log (n+1)\right\rceil$，因为一棵根的 $\mathrm{dis}$ 为 $x$ 的二叉树至少有 $x-1$ 层是满二叉树，那么就至少有 $2^x-1$ 个节点。**注意这个性质是所有二叉树都具有的，并不是左偏树所特有的。** - 每个节点左儿子的 $\mathrm{dis}$ 都大于等于右儿子的 $\mathrm{dis}$。 所以左偏树每个节点的 $\mathrm{dis}$ 都等于其右儿子的 $\mathrm{dis}$ 加一。 #### 注意：dis不是深度，左偏树的深度没有保证，一条向左的链也是左偏树。 ### 合并 定义 `merge(x,y)` 为合并两个堆，返回根节点编号。 为方便这里讨论小根堆。 由于左偏树中左儿子的距离大于右儿子的距离，我们每次将 $y$ 与 $x$ 的右儿子合并来保证树的平衡。 注意合并后要更新左右节点的位置和 $\mathrm{dis}$。 ```cpp int merge(int x,int y){ if(!x||!y) return x|y; if(val[x]>val[y]) swap(x,y);//小根堆 rc[x]=merge(rc[x],y); if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]); dis[x]=dis[rc[x]]+1; return x; } ``` ### 插入节点 单个节点也可以视为一个堆，合并即可。 ### 删除根 合并根的左右儿子即可。 ### [P3377 【模板】左偏树（可并堆）](https://www.luogu.com.cn/problem/P3377) 双倍经验：[P2713 罗马游戏](https://www.luogu.com.cn/problem/P2713) ### 完整代码 ```cpp #include <bits/stdc++.h> using namespace std; const int N=1e5+5; int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int n,m; int val[N],dis[N],lc[N],rc[N],fa[N]; bool isdel[N]; int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } int merge(int x,int y){ if(!x||!y) return x|y; if(val[x]>val[y]) swap(x,y); rc[x]=merge(rc[x],y); if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]); dis[x]=dis[rc[x]]+1; return x; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++){ val[i]=read(),fa[i]=i; } while(m--){ int op=read(); if(op==1){ int x=read(),y=read(); if(isdel[x]||isdel[y]) continue; x=find(x),y=find(y); if(x!=y) fa[x]=fa[y]=merge(x,y); } if(op==2){ int x=read(); if(isdel[x]){puts("-1");continue;} x=find(x); printf("%d\n",val[x]); isdel[x]=true; fa[lc[x]]=fa[rc[x]]=fa[x]=merge(lc[x],rc[x]); lc[x]=rc[x]=dis[x]=0; } } return 0; } ``` ### 相关习题 - [P1456 Monkey King](https://www.luogu.com.cn/problem/P1456) ### 注意 左偏树的深度可能达到 $\mathcal{O}(n)$，因此找一个点所在的堆顶要用并查集维护，不能直接暴力跳父亲。（虽然很多题数据水，暴力跳父亲可以过……） ### [P1552 [APIO2012] 派遣](https://www.luogu.com.cn/problem/P1552) ### 题意简介 一棵节点为 $n$ 的树，每个点上有费用和价值。定义满意度为一个节点的价值乘节点子树所选点个数（点在子树内任意选，可选根），所选点价值和不超过 $m$。最大化满意度。$1 \le n \le 10^5,1 \le m \le 10^9

Solution

正面做比较不好想，于是考虑自下而上的合并过程。

会发现一个性质：每个节点的最优选择中所有的点（除了根节点）都是它子树最有选择的点。

证明也不难：因为如果选择其他更优的点，那子树中必定选择它。

那么久可以开始合并堆了，把每个点看成一个堆，分别和其他儿子合并。

因为预算有限，我们使用大根堆，当预算不足时踢出最贵的，这样就可以得出当前节点的最大满意度。

由于上述性质，踢出的点可以永不被选择，所以正确性可以保证。

没怎么卡常，但是感觉可以递归改递推减少不少常数，不过懒得卡了，递推版看这一篇。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int n,m;
int val[N],dis[N],lc[N],rc[N],fa[N];
int L[N];
vector<int>e[N];

int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

int merge(int x,int y){
    if(!x||!y) return x|y;
    if(val[x]<val[y]) swap(x,y);
    rc[x]=merge(rc[x],y);
    if(dis[lc[x]]<dis[rc[x]]) swap(lc[x],rc[x]);
    dis[x]=dis[rc[x]]+1;
    return x;
}

int sz[N],rt[N];
long long sum[N],ans;
void dfs(int u){
    sz[u]=1,sum[u]=val[u],rt[u]=u;
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        dfs(v);
        sz[u]+=sz[v],sum[u]+=sum[v];
        rt[u]=merge(rt[u],rt[v]);
    }
    while(sum[u]>m&&sz[u]){
        --sz[u],sum[u]-=val[rt[u]];
        rt[u]=merge(lc[rt[u]],rc[rt[u]]);
    }
    ans=max(ans,1ll*L[u]*sz[u]);
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=n;i++){
        e[read()].push_back(i);
        val[i]=read(),fa[i]=i;
        L[i]=read();
    }
    dfs(1);
    printf("%lld\n",ans);

    return 0;
}

相关习题

参考资料