D2T3 树形图
首先判掉一些 case
将任意一个 \(1\) 类点定为根，求出一棵 dfs 树，则图上的非树边只有返祖边，没有横叉边。
\(1\) 类点
考虑在这棵 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\) 类点。
如果一个 \(x\) 为 \(1\) 类点，那么一定有恰好一条返祖边 \(u\to v\) 覆盖了 \(fa_x\to x\)，并且这条返祖边不能删除，否则 \(x\) 的子树就会脱离这个强连通分量，从而不再是 \(1\) 类点。
于是我们得到了若干条返祖边不能删除的限制。
对于
标签：返祖,题解,类点,dfs,fa,边覆盖,NOI2024 From： https://www.cnblogs.com/Rainbowsjy/p/18318106