题解：AT_agc070_b [AGC070B] Odd Namori

容斥宇宙题。

考虑题面的三条限制。对于限制一，相当于图是一个内向基环树森林，与长度为 $n$ 值域为 $[1,n]$ 的序列构成双射，接下来我们称与当前图对应的序列为 $p$。

对于限制二我们容易想到容斥：钦定若干环，奇环的容斥系数为 $1$，偶环的容斥系数为 $-1$。这样一个图如果有一个偶环，那么偶环选或不选之间的系数抵消，贡献是 $0$；一个图如果没有偶环，那么奇环的系数恰好是 $2^{环的数量}$，很好！

但是我们暴力枚举若干个环再计数太劣了。我们设钦定在环上的点构成的集合为 $S$，若 $|S|\geq 2$，选出编号最小和次小的点 $u,v$，然后交换 $p_u$ 和 $p_v$。

由于交换操作的性质，操作后的图与原图构成双射，而无论是把一个奇环拆成奇环和偶环，还是把两个奇环合并成偶环，容斥系数都恰好 $\times -1$，所以所有 $|S|\geq 2$ 的钦定方案的贡献的和 $=0$。

对于 $|S|=1$ 的方案是好求的，放在序列上相当于钦定 $p_{i}=i$，答案是 $n\times n^{n-1}=n^n$。

考虑有限制三怎么做，我们尝试像上面一样交换 $p$ 的两个元素构成双射。

还是讨论 $S$，希望能通过交换构成双射，又因为容斥系数恰好 $\times -1$ 就能抵消了。

若 $S$ 上的点在树上构成了 $\geq 2$ 个连通块，选出 连通块的根 中编号最小和次小的点 $u,v$ 交换即可。首先由于交换不会改变 $S$，也就不会改变 $S$ 构成 连通块的根 这个集合。然后，操作之后显然仍然满足限制三。

所以只需要考虑 $S$ 在树上构成 $1$ 个连通块。选出最小的有序对 $(u,v)$，满足 $\text{fa}_u=\text{fa}_v$ 并交换，与上面同理构成双射。

所以 $S$ 只能构成一条 祖先-后代 链，设深度最浅的点为 $u$，其儿子为 $v$，若 $p_u\ne u$，交换 $p_u$ 和 $p_v$ 同理能构成双射。此时只考虑 $p_u=u$，再令 $u$ 为深度第二浅的点，其儿子为 $v$……

我们可以一直进行下去，直到 $\forall x\in S,p_x=x$，此时 $S$ 内部的方案数就是 $1$。其他点的答案是 $(n-1)^{n-|S|}\times [1\notin S]\frac{n}{n-1}$，因为 $p_{1}$ 可以选 $n$ 个数而其他点由于有父亲只能选 $n-1$ 个数。

此时我们可以写出一个 $O(n^2)$ 的做法了，暴力枚举这条链即可。我们枚举 $S$ 最深的点 $x$，发现答案只跟 $\text{dep}_x$ 有关，所以推导一下发现只需要预处理 $\sum_{i=1}^d (n-1)^i$ 即可。

时间复杂度 $O(n)$。