Exercise 1
设 $n = 2^k$。依次执行以下 union 操作：
- $\text{union}(1,2),\ \text{union}(3,4),\ \dots,\ \text{union}(n-1,n)$
- $\text{union}(1,3),\ \text{union}(5,7),\ \dots$（将上一步中相邻的根合并）
- 重复上述过程，直到最后执行 $\text{union}(1, n/2+1)$，得到一棵高度为 $k$ 的树。
然后执行 $\text{find}(1)$。由于没有路径压缩，该 find 需要访问 $k = \log_2 n$ 个节点，耗时 $\Omega(\log n)$。总操作数 $m = n-1 + 1 = n$。
Exercise 2
先考虑最终稳定后的树：记此时秩为k的节点集为 $S_{k}$ 。考虑某个时刻节点u的秩变为了k，则其在最终稳定后的树的秩一定大于等于k；反之同理，最终稳定时一个节点u的秩大于等于k，则在某一个时刻其秩等于k。所以在某个时刻秩为k的节点就是最后稳定时秩大于等于k的节点。考虑这些节点最后一次作为根的时刻，此时它们的子树大小都 $\geq 2^k$ ，且每个子树都不相交。所以这些点的数量 $\leq \frac{n}{2^k}$。
Exercise 3
$$ \pi(3) = 4,\pi(1,2,4,5,6,7,8)=8 $$ $$ \begin{align} rank(8)=3 \\ rank(4)=2 \\ rank(2)=1 \\ rank(6)=1 \end{align} $$其余的rank为0。
Exercise 4
对操作序列的长度进行归纳。
初始时，每个元素都是根且秩为 0，两种实现相同。
假设前t次操作后结论成立。考虑第t+1 次操作。
若为 find(x)： 无路径压缩时，结构不变。有路径压缩时，仅将x到根的路径上的节点直接指向根，但每个节点的秩不变，根的身份也不变。因此结论仍成立。
若为 union(x,y)： 设 $r_{x},r_{y}$ 分别为两种实现中 x,y 的根。由归纳假设，两种实现中 $r_{x},r_{y}$ 相同，且它们的秩相同。按秩合并规则，两种实现会得到相同的根 $r$ ，并且 $r$ 的新秩相同（若原秩相等则加 1，否则取较大者）。其余节点的秩和根状态不变。因此结论成立。
由归纳法，(a) 和 (b) 得证。