自动搬运

查看原文

来自洛谷，原作者为

	Rainbow_qwq **

搬运于2025-08-24 23:01:16，当前版本为作者最后更新于2024-07-23 22:14:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

D2T3 树形图

首先判掉一些 case：先 tarjan 一遍求出强连通分量，找到一个能到达所有点的强连通分量（也可能找不到），那么 $1,2$ 类点只可能在这个强连通分量中。

若其中没有 $1$ 类点，则强连通分量内所有点都为 $2$ 类点。

$1$ 类点的性质是：将任意一个 $1$ 类点定为根，求出一棵 dfs 树，则图上的非树边只有返祖边，没有横叉边。

求出 $1$ 类点

以任意一个 $1$ 类点定为根，求出一棵 dfs 树。考虑在这棵 dfs 树的基础上求出所有 $1$ 类点：

考虑 $fa_u\to u$ 这条边被几条返祖边覆盖了，由于这是一个强连通分量，所以子树中至少有一条返祖边覆盖 $fa_u\to u$。

若有 $\ge 2$ 条返祖边覆盖了 $fa_u\to u$，则 $u\to fa_u$ 有至少两种方案能走到，$u$ 必然不为 $1$ 类点。

若只有 $1$ 条返祖边覆盖了 $fa_u\to u$，设这条边为 $x\to y$，则 $u$ 子树中的点向上走必然要走到 $y$，$u$ 是否为 $1$ 类点等价于 $y$ 是否为 $1$ 类点。于是可以从上到下递推出所有 $1$ 类点。

求出 $2$ 类点

仍然在这棵 dfs 树的基础上求出 $2$ 类点。

如果一个 $u$ 为 $1$ 类点，那么一定有恰好一条返祖边 $x\to y$ 覆盖了 $fa_u\to u$，并且这条返祖边不能删除，否则 $x$ 的子树就会脱离这个强连通分量，从而不再是 $1$ 类点。

于是我们得到了若干条返祖边不能删除的限制。

假设我们想判定 $u$，也就是删去若干条边把 $u$ 变为 $1$ 类点，则我们想删去覆盖了 $fa_u\to u$ 的若干条返祖边，使得只剩下一条 $(x,y)$ 覆盖了 $fa_u\to u$，并且 $y$ 也是 $1/2$ 类点，那么 $u$ 就可以成为 $2$ 类点了。

对于一个点 $u$，仍然考虑 $u\to fa_u$ 这条边：

若被两条不能删除的返祖边覆盖，则 $u$ 一定不可行。

若被一条不能删除的返祖边覆盖：设这条边为 $x\to y$，则 $u$ 是否为 $2$ 类点等价于 $y$ 是否为 $1/2$ 类点。

若被零条不能删除的返祖边覆盖：那么 $u$ 子树中有若干条能删除的返祖边。若能找到一条能删除的返祖边 $x\to y$，使得 $y$ 为 $1/2$ 类点，则 $u$ 就可以为 $2$ 类点。

如何找一个 $1$ 类点

考虑以 $1$ 类点为根构成的 dfs 树的性质。观察其叶子，由于没有横叉边，所有叶子必然满足入度为 $1$。

对于所有入度为 $1$ 的点 $u$，假设有边 $v\to u$，则可以把 $u$ 向 $v$ 合并。具体来说，把 $u$ 的出边并到 $v$ 的出边里（所有 $u\to x$ 改为 $v\to x$，不需要去除重边，但要删去自环），然后删除点 $u$。也就是在 dfs 树上不断缩叶子的过程。

BFS 不断执行这个过程，并把新出现的入度为 $1$ 的点加入队列里。

在若干轮删除之后，若只剩下 $1$ 个点，则这个点即可作为 $1$ 类点；否则若某个时刻每个点入度都 $\ge 2$，则不存在 $1$ 类点。

使用启发式合并维护边集，时间复杂度 $O((n+m)\log n)$。

可以用 vector 存下每个点的入边和出边，合并时按两个 size 的和加权，取更小的点的所有边合并到大的点上，这样在合并时就可以计算有多少条 $u-v$ 的边。