- 合并两个堆并维护最小或最大性质
- 解决树上节点问题,从叶节点往根维护,每个节点看作一个堆
- 表示到最近的叶节点的距离
- ,所以每次对合并(树高矮)
- 表示堆的顶点对应下标
- 关键代码
-
static void dfs(int x){ for(int i=head[x];i>0;i=e[i].nxt){ int y=e[i].to; dfs(y); fa[x]=merge(fa[x],fa[y]); } while(s[fa[x]]<h[x]&&fa[x]!=0){//根据条件,删除堆顶 //pushdown……懒标记 fa[x]=merge(ls[fa[x]],rs[fa[x]]); } } static int merge(int x,int y){ if(x==0||y==0)return x+y; //pushdown…… if(s[x]>s[y]){//判定小于条件(小根堆) int t=x;x=y;y=t; } rs[x]=merge(rs[x],y); if(hi[ls[x]]<hi[rs[x]]){ int t=ls[x];ls[x]=rs[x];rs[x]=t; } hi[x]=hi[rs[x]]+1; //pushup……维护子树和,子树大小…… return x; }
-
若多个指定同一节点
-
for(int i=1;i<=m;++i){ fa[c[i]]=merge(fa[c[i]],i);//直接维护节点堆 }
-
因为在树上操作从叶子到根,直接就是堆顶
-
若是要查找指定点所在堆的堆顶,需要跳,采用路径压缩加速
-
注意删除时对的维护
-
fa[ls[x]]=fa[rs[x]]=fa[x]=merge(ls[x],rs[x]);