Mergers：确定性线性时间算法
给定一棵有 $n$ 个顶点的树，每个顶点属于 $k$ 个州之一。每次可以合并两个州，求使整棵树无法按州划分为两个非空连通部分的最少操作次数。
通过 DFS 区间上的颜色首末位置，可以在 $O(n+k)=O(n)$ 时间、$O(n+k)$ 空间内解决本题。
一、归约到缩边后的叶子数
把州称为颜色。删除一条树边后，若没有任何颜色同时出现在两侧，称它为“可切边”；否则称为“不可切边”。题意等价于合并颜色，使所有边都不可切。
先缩掉全部不可切边，得到树 $T'$。同一种颜色的所有点一定在同一个缩点中，因为连接同色点的路径上的每条边都不可切。一个缩点可以包含多种颜色，缩点只是分析工具，不代表已经实际合并这些颜色。
合并两个颜色，恰好使它们所在缩点之间的路径变为不可切。因此，我们要用尽量少的路径覆盖 $T'$ 的所有边。设 $T'$ 的度为 $1$ 的点有 $L$ 个，则答案为 $\lceil L/2\rceil$；只有一个缩点时 $L=0$，答案为 $0$。
下界： 一次缩路径至多使叶子数减少两个，因此至少需要 $\lceil L/2\rceil$ 次。
上界： $L=2$ 时直接选择整条路径。$L\ge3$ 时，以非叶子为根，将叶子按 DFS 顺序排列。每条边的一侧的叶子构成连续区间，两侧都非空。若 $L$ 为奇数，在某个叶子旁边插入它的一份副本；否则不变，得到偶数个位置 $M=2\lceil L/2\rceil$。副本只是重复使用一个叶子。
把位置 $i$ 和 $i+M/2$ 配对，$1\le i\le M/2$。对于任意边，两侧的叶子在循环序列上形成两个非空连续圆弧。较短的圆弧长度至多为 $M/2$，不可能同时包含一对相隔 $M/2$ 的位置。因此至少有一对叶子分处该边两侧，对应路径覆盖此边。全部 $M/2$ 条路径覆盖所有边。
依次合并每对叶子中选出的颜色；若两者已合并，跳过即可。这至多用 $\lceil L/2\rceil$ 次操作，且使每条边两侧都有相同颜色，故上界成立。
二、用 DFS 区间判断颜色是否跨边
任意定根，用 DFS 前序编号 $tin[u]$。子树 $u$ 对应连续区间
$$I_u=[tin[u],right[u]].$$
对每个颜色 $c$，记录它在整棵树 DFS 序上的首末出现位置：
$$first[c]=\min_{color[x]=c}tin[x],\qquad last[c]=\max_{color[x]=c}tin[x].$$
对子树汇总：
$$low[u]=\min_{x\in subtree(u)}first[color[x]],$$
$$high[u]=\max_{x\in subtree(u)}last[color[x]].$$
对于非根点 $u$，它与父亲的边可切，当且仅当
$$\boxed{low[u]\ge tin[u]\quad\text{且}\quad high[u]\le right[u].}$$
充分性： 子树里出现的每种颜色，其全局首末位置都在子树区间内。因此该颜色的所有出现都在区间内，没有颜色跨边。
必要性： 若没有颜色跨边，则子树里每种颜色都完整包含于子树中，其首末位置满足边界；取最小值与最大值后仍满足判定式。
同色点在 DFS 序中可以不连续，我们只利用子树是连续区间这一事实。极值必须取遍子树所有点的颜色，不能只检查根点自己的颜色。
先初始化
low[u] = first[color[u]]
high[u] = last[color[u]]
right[u] = tin[u]按 DFS 序逆序处理非根点 $u$，它的所有后代已经处理完。判断父边后，向父亲 $p$ 汇总：
low[p] = min(low[p], low[u])
high[p] = max(high[p], high[u])
right[p] = max(right[p], right[u])这样每条边只用常数次操作即可判定。
三、同一遍后序中统计叶子
无需真正构建缩树。定义 $down[u]$：在 $u$ 子树内部缩掉不可切边后，包含 $u$ 的那个连通块向下连接的可切边数量，不包含父边。初值全部为 $0$。
仍按 DFS 序逆序处理非根点 $u$，父亲为 $p$：
- 父边可切：该连通块不再向上合并，最终度数为 $down[u]+1$。因此 $down[u]=0$ 时计入一个叶子，并令 $down[p]$ 加一。
- 父边不可切：这个连通块并入父亲所在连通块，执行 $down[p]\mathrel{+}=down[u]$。
再把上一节的三个极值传给父亲。每个非根缩点有唯一向上的可切边，因此恰好在那条边下方统计一次，没有遗漏或重复。
最后根所在连通块没有父边，恰在 $down[root]=1$ 时再计一个叶子。若全部边都被缩掉，根的度数为 $0$，叶子数为 $0$，输出 $0$；$n=1$ 也包含在其中。
四、实现与复杂度
- 用显式栈进行 DFS，得到 $order,parent,tin$，避免 $500000$ 个点的链使递归栈溢出。栈后进先出，即使一次压入所有孩子，一个孩子的全部后代也会先于下一个兄弟处理，因此子树仍形成连续 DFS 区间。
- 扫描 $order$ 求每种颜色的 $first,last$。
- 初始化每个点的 $low,high,right,down$。
- 逆序扫描 $order$，同时分类父边、汇总子树极值、统计叶子。
- 输出 $(L+1)/2$（整数除法）。
邻接表有 $2(n-1)$ 条记录，所有扫描及每条边的处理均为常数工作，颜色数组初始化为 $O(k)$。总时间严格为 $O(n+k)=O(n)$，空间为 $O(n+k)=O(n)$。这是确定性最坏情况界，没有哈希碰撞风险或并查集摊还项。
五、与标准解法对比
官方解说 PDF 第 38—40 页给出 LCA 加树上差分的 $O(n\log n)$ 解法，第 41—43 页另给出 $O(n\alpha(n))$ 并查集缩边法。jiangly 的 QOJ 题解 同样列出了这两个界。
本文保留其答案归约，把“子树是否完整包含其中每种颜色”转化为首末位置极值比较，再用后序边界数统计缩树叶子，得到严格线性界。相较于上述两种标准解法，时间复杂度分别省去了 $\log n$ 与 $\alpha(n)$ 因子。