从并查集的按秩合并看一类构造性问题

以下讨论建立在不进行路径压缩的情况下。

众所周知，并查集有两类按秩合并的方式，这里以深度为例：

inline void unite(int p,int q)
{
	p=find(p),q=find(q);
	if(dep[p]>dep[q])fa[q]=p;
	else fa[p]=q;
	if(dep[p]==dep[q])dep[q]++;
}

仔细观察一下我们的代码，可以发现 (oldsymbol p) 的深度是不可能发生变化的。

但在正常情况下，当两棵树深度相同时，可以随便将一棵接到另一棵的根下面。

也就是说在一定条件下我们可以控制某些点的深度。

比如要把某些深度弄到某个数量：

• 给定合并顺序，构造满足条件的方案。
• 自己构造操作求需要的最小点数。
• 给定操作，可以随便换顺序，但钦定了深度相同时哪个点会作为根，构造满足条件的方案。

暂时就想到这三个。