题解：树上的城市连通性与强连通分量应用

问题分析

本题要求通过合并城市，使得存在一个城市可以作为首都。首都的条件是：该城市的任意小镇都只能通过属于该城市的小镇到达。

换句话说，如果一个城市 $x$ 要成为首都，那么：

1. 所有属于城市 $x$ 的小镇在树上是连通的
2. 这些小镇形成一个连通子图
3. 这个连通子图与外界的所有连接都必须通过城市 $x$ 内部的小镇

关键观察

1. 城市作为首都的条件
   设城市 $x$ 的小镇集合为 $S_x$。$x$ 可以作为首都当且仅当 $S_x$ 的导出子图是连通的，并且从 $S_x$ 到其他部分的所有路径都必须经过 $S_x$ 中的点。
   实际上，这意味着 $S_x$ 必须包含其所有小镇在树上的最小斯坦纳树的全部节点。

2. 合并操作的影响
   合并两个城市 $x$ 和 $y$ 相当于将 $S_y$ 中的小镇划归给 $x$。我们的目标是找到最少的合并次数，使得某个城市满足首都条件。

3. 转化为图论问题
   可以建立一个有向图，其中顶点是城市。如果城市 $x$ 的某个小镇的父节点（在树中）属于城市 $y$，那么从 $x$ 到 $y$ 连一条有向边。
   这意味着：如果 $x$ 要成为首都，那么所有能从 $x$ 到达的城市都必须被合并到 $x$ 中。

算法框架

第一步：预处理

1. 读取输入，建立树的邻接表
2. 对树进行 DFS，得到每个节点的 DFS 序和子树区间 $[dfn[x], dfn1[x]]$
3. 对于每个城市，记录其包含的所有小镇

第二步：建立城市间的有向图

对于每个城市 $i$：

1. 找到该城市所有小镇中 DFS 序最小的那个（记为 $id$）
2. 检查是否所有该城市的小镇都在 $id$ 的子树内：
   • 如果是：则对于 $id$ 本身，不需要连边
   • 如果不是：则 $id$ 也需要参与连边
3. 对于该城市的每个小镇 $x$（根据上一步的条件决定是否包含 $id$），连接 $c[x] \to c[fa[x]]$，其中 $fa[x]$ 是 $x$ 在树中的父节点

第三步：求强连通分量

1. 在建立的有向图上运行 Tarjan 算法，求出所有强连通分量
2. 每个强连通分量代表一组必须合并的城市

第四步：计算答案

1. 统计每个强连通分量的大小（包含的城市数）
2. 标记那些有出边指向其他分量的分量（不能作为首都候选）
3. 对于没有出边指向其他分量的分量（即汇点分量），其大小减 1 就是需要合并的次数
4. 取所有汇点分量的最小值作为答案

正确性证明

1. 边建立的正确性
   如果城市 $x$ 的小镇 $v$ 的父节点属于城市 $y$，那么要使 $x$ 成为首都，必须将 $y$ 合并到 $x$ 中（或者更一般地，所有能从 $x$ 到达的城市都必须合并到 $x$）。

2. 强连通分量的意义
   在一个强连通分量中，任意两个城市 $x$ 和 $y$ 都能互相到达。这意味着它们必须被合并到同一个城市中。

3. 汇点分量的性质
   一个没有出边的强连通分量，意味着其中的城市不依赖于任何其他城市。因此，可以将该分量中的所有城市合并成一个，作为首都候选。

4. 答案计算
   如果汇点分量包含 $m$ 个城市，那么需要 $m-1$ 次合并（将其他 $m-1$ 个城市合并到剩下的一个城市中）。

复杂度分析

• 时间复杂度：$O(N + K)$
  • DFS 遍历树：$O(N)$
  • 建立有向图：$O(N)$
  • Tarjan 算法：$O(K + E)$，其中 $E \le N$
• 空间复杂度：$O(N + K)$

对于 $N \le 2\times 10^5$ 的数据范围完全可行。

总结

本题是一道树与有向图强连通分量结合的巧妙题目，主要考察：

1. 问题转化能力：将树上的城市合并问题转化为有向图的强连通分量问题
2. DFS 序的应用：利用 DFS 序高效判断节点是否在子树内
3. Tarjan 算法：求解强连通分量
4. 建模思维：将"首都条件"转化为有向图中的可达性关系

算法的核心在于认识到：要使一个城市成为首都，所有它能到达的城市都必须被合并进来。通过建立城市间的依赖关系图，并求强连通分量，我们能够找到最小的合并方案。

这种"树结构转化为有向图，再通过强连通分量求解"的方法在竞赛问题中并不常见，体现了出题人的巧思，也展示了图论问题的多样性和灵活性。