NOI2024 树形图 graphee

· · 题解

D2T3 树形图

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

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

### 求出 $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$ 的边。