没挂分，掉 rp。

A：

整体二分，考虑二分最小值，每次用并查集维护连通性，集合大小即为第二问答案，由于会出现回退，所以并查集要用启发式合并。

还有其他做法，不太懂。

B：

原题链接

推市 子题，懒得打了。

C：

首先暴力连边，缩完点后每个点内所有点两两成对，点与点之间不会产生贡献。

可以用线段树维护 $dfn$，线段树的节点上用 $vector$ 按 $dep$ 升序存储 $[l,r]$ 内所有点的信息，而且 $vector$ 内的信息向真实的点连边，$vector$ 内的点向比它小的相邻的点连边。

那么我们可以将一个子树按 $dfs$ 序划分成若干区间，对于每段区间，二分查找到最后一个满足 $dep$ 的点连边。

也可以用 K-D tree 优化建图，将所有点 $dfs$ 序设为 $x$，编号设为 $y$，连边就变成每个点向后一个矩形连边，边数为 $N\sqrt N$。