Card

推荐基环树题目（不涉及建模）：NOI2013T6（fast food）,NOIP2018T4、NOIP2023T2。

这题的建模很神秘，我是看TJ的。泪目了。

题意是：有 $n$ 个二元组 $(a_{i,0}, a_{i,1})$ ，和长度为 $n$ 的数组 $c$。初始 $c_i = 0, 1 \le i \le n$。你可以将 $c$ 中的元素变成任意自然数。满足将集合 $|\{a_{1, c_1 \bmod 2}, a_{2, c_2 \bmod 2}, \dots , a_{i, c_i \bmod 2}\}| = n$。先判断有没有解，随后计算满足条件 $\min (\sum (c))$，并计算取到这个值的条件下不 $c$ 的个数。

显然，$\forall i ,0 \le c_i \le 1$。

注意到如果令 $a_{i, 1} \to a_{i, 0}$ 连边，则满足条件的图（连通块）满足入度不大于 $1$，操作等价将边置换。那么如果连通块不是一棵树，且不是基环树就无解了。

随后对树，基环树分类。

如果是一棵树，最终的结果必然是外向树。所以我们枚举根节点并钦定他为根计算最小代价，方案数只有 $1$ 种，累加就行。需要用到换根DP。

令 $f_1$ 是答案。

• $f_1$ 是以 $1$ 为根节点有几条边要置换
• $f_v = f_{fa} + 1$ 如果在以 $fa$ 为根的时候，$fa\to v$ 不必置换.
• $f_v = f_{fa} - 1$ 如果在以 $fa$ 为根的时候，$fa\to v$ 必置换.

答案极为最小的 $f$ ，方案数是最小值的个数。

对于基环树，先仅仅考虑环，你发现只有顺时针、逆时针两种本质不同的情况。

在考虑环点的树，它们只能钦定环点为根，因为环上所有点的入度均为 $1$，相当于前面的 DP，不带换根。

注意点数为 $2$ 的环。

细节我写一点：

1. 遍历的时候要把有向边看成无向边。
2. 你要实现基环树的找环，且环上点均要找到。
3. 多个连通块分别考虑
4. 对于答案，内部是最小值取小，相等才加方案数。外部是最小值相加，方案数相乘。因为连通块是独立的.
5. 本题数组开 $2\times 10^5$ 即 $2n$。