模板

学习 top tree，据说是全局平衡二叉树的进阶。

一棵树能够通过缩二度点和缩一度点使得这棵树点数变成

2

，我们称缩二度点为 Compress 操作，缩一度点为 Rake 操作。

Compress(X)：

Rake(X)：

通过 Compress 和 Rake 缩一棵树的示例：

定义一个簇为一个连通边集，则 Compress 和 Rake 可以定义在簇上。簇只存贮完全包含在簇内的点和边的信息，与其它簇共用的点的信息是不储存的。我们称完全包含在簇内的点为内点，完全包含在簇内的边为内边，和其它簇共用的点为端点。那么根据上述定义，一个簇有且仅有两个端点（一开始每个簇两个端点，而 Rake 和 Compress 之后还是两个），我们称原树上这两个端点之间的路径为簇路径。

考虑簇的 Rake 操作和 Compress 操作都只会涉及到一个端点相交，所以簇的一些信息合并是非常简单的。我们引入 top tree 的概念，它和点分树是很像的，都描述了一个过程，top tree 就是簇的合并过程构成的树。每个簇的叶子都是原树的一条边构成的簇，我们称这种簇为基簇；top tree 的根就是原树最终合并出来的形态，我们称这个簇为根簇。如果我们对某个点或边进行了修改，那么我们就可以在 top tree 上将它到根的 Rake/Compress 操作再做一遍，即可更新整棵树的信息了。

然而随意的合并过程可能导致 top tree 的树高没有保证，复杂度错误，我们需要一种正确的合并方式。注意到重链剖分中的维护轻儿子信息等效于 Rake，维护重链信息等效于 Compress，我们考虑借用树剖的过程来表示 top tree。以下是一份代码实现：

CPP

inline void pushup(int u){!tr[u].tp?rake(tr[u],tr[tr[u].l],tr[tr[u].r]):compress(tr[u],tr[tr[u].l],tr[tr[u].r]);}
//tp=0 表示 Rake，tp=1 表示 Compress
int build(vector<pair<int,int> >&V,int l,int r,int tp){
	if(l==r)return V[l].first;
	int mid=l-1,s=0;
	for(int i=l;i<=r;i++)s+=V[i].second;
	while(s>0&&mid+1<r)mid++,s-=V[mid].second*2;
	int u=++idx;
	tr[u].l=build(V,l,mid,tp),tr[u].r=build(V,mid+1,r,tp),tr[tr[u].l].fa=tr[tr[u].r].fa=u,tr[u].tp=tp;
	pushup(u);return u;
}//按照簇的点集大小加权建树，这里的树是 leafy 的
void dfs1(int u,int from){
	sz[u]=1,fa[u]=from;
	for(int i=he[u];i;i=e[i].ne){
		int v=e[i].to;if(v==from)continue;
		dfs1(v,u),sz[u]+=sz[v];
		if(sz[v]>sz[son[u]])son[u]=v;
	}
}
int dfs2(int u,int from){
	vector<pair<int,int> >V;V.eb(mk(u,1));
	for(int v=u;son[v];v=son[v]){
		vector<pair<int,int> >E;E.eb(mk(son[v],1));
		for(int i=he[v];i;i=e[i].ne){
			int w=e[i].to;if(w==fa[v]||w==son[v])continue;
			E.eb(mk(dfs2(w,v),sz[w]));
		}
		V.eb(mk(build(E,0,E.size()-1,0),sz[v]-sz[son[v]]));//对所有轻儿子建树，类型为 Rake
	}
	return build(V,0,V.size()-1,1);//对整条链建树，类型为 Compress
}

这棵树的树高是

O(\log n)

的，证明过程同全局平衡二叉树。

那么 top tree 能干的事情就很多的，比如它是点分树的上位替代，求直径之类的事情都可以做。

例题

传送门

维护直径很好做，但是 top tree 还能维护带添加删除点集的两两最短距离，薄纱点分树。

我没看小说啊怎么办（静态 top tree）

文章操作

模板

例题

相关推荐

评论

我没看小说啊怎么办（静态 top tree）