CF2002D2 DFS Checker

有结论，如果 $fa(dfn_{i+1})$ 是 $dfn_i$ 的祖先，那么满足 $dfn$ 是合法的，做完了。

CF1835D Doctor's Brown Hypothesis

一个实现不太一样的做法。

因为需要分别存在 $x\to y$ 和 $y\to x$ 的路径，所以满足题目要求的 $(x,y)$ 肯定是在一个 SCC 中的。

对于每一个 SCC 分开考虑，最后将结果相加即可，下面讨论的图都是强连通的。

假设图中所有的环的长度为 $len_1,len_2,\cdots,len_m$，那么记 $d=\gcd\limits_{i=1}^m len_i$。

下面讨论的图都是在在对 $d$ 取模意义 下的。

在下的 SCC 中有一些性质：

如果存在一条路径 $a\to b$，而且边权为 $w$，那么就可以构造出 $b\to a$ 而且边权为 $-w$ 的路径。

证明：

因为 $a,b$ 在同一个强连通分量内，所以它们必然在一个环中，假设这个环的边权和为 $s$。那么从 $b$ 出发绕着环走 $t$ 圈，这样的贡献就是 $s\times t$ 也就是 $0$。

所以只要在最后一圈的时候直接停在 $a$ 那么就相当于构造出了一条 $b\to a$ 的边权为 $-w$ 的路径。

另外有一个性质，如果强连通分量上有一个环，那么所有的点都可以看作在这个环上。

证明：

假设 $a$ 在长度为 $x$ 的环上，而 $b$ 不在。

假设 $a\to b$ 的路径长度为 $w$，那么根据上面的性质，显然 $b\to a$ 的长度就是 $w$。

那么就可以构造 $b\to a\to b$ 的路径，在到达 $a$ 之后可以随意的在环上行走，而结束后又可以原路返回。容易理解，这样路径的长度为 $w+x+(-w)=x$。

换而言之：

$x\to y$ 的一条复杂路径可以表示为 $x\to y$ 的简单路径的长度加上 $\sum\limits_{i=1}^m a_i\times len_i$，其中 $\forall a_i\in \mathbb{N}$。

这样就解决有些 $a_i=0$ 但是却经过了一些其他必须要经过 $i$ 的环才能到达的环的问题。

最后还有一个性质，如果有一条 $x\to y$ 的路径长度为 $Len$，那么不管最初的简单路径怎么选择，其长度在模 $d$ 意义下都可以做到为 $Len$。

证明：

由第一个性质可以做出构造，先让长度为 $a$ 的路径走负边权的路原路返回再走一次长度为 $b$ 的路，这样结果就是 $a+(-a)+b=b$ 了。

考虑如何求解一个所有的环长的 $\gcd$。

对于一个 SCC 跑一个叶向生成树，显然环有两种情况：一条非树边和一些树边组成，多条树边和一些树边组成。

因为第二种情况，这些环的长度都可以通过第一种环通过加减得到，所以显然不会对 $\gcd$ 产生影响。

具体的 $\gcd(a,b)=\gcd(a,b,a+b)$，证明如下：

设 $\gcd(a,b)=g$，那么 $a=\frac{a}{g}\times g$，$b=\frac{b}{g}\times g$，所以就有 $a+b=g\times ({\frac{a}{g}+\frac{b}{g}})$。

于是就遍历这个 dfs 树，如果遇到了返祖边那么就更新 $\gcd$。

回到这个题目的具体要求，假设 $x\to y$ 的简单路径长度为 $Len$，那么题目的要求就是：

$Len+\sum\limits_{i=1}^m a_i\times len_i\equiv k \pmod{d}$

因为 $\forall i\in[1,m]\cap\mathbb{Z}$ 都满足 $d\mid len_i$，所以 $\sum\limits_{i=1}^m a_i\times len_i\equiv 0\bmod{d}$，也就得到了其实题目的要求是 $Len\equiv k$。

因为 $x\to y$ 的长度和 $y\to x$ 的长度需要一样，所以我们先考虑判断 $\text{dis}(x\to y)\equiv \text{dis}(y\to x)\pmod d$。

因为第三个性质，所以不妨我们直接让 $x$ 走到 $rt$ 然后再走到 $y$，反之同理。

因为 $x\to y$ 的边权为 $w$ 那么 $y\to x$ 的边权就为 $-w$，所以就相当于判断：

$-\text{dis}(rt,x)+\text{dis}(rt,y)\equiv \text{dis}(rt,x)-\text{dis}(rt,y)\pmod d$

因为 $x$ 和 $y$ 到 $rt$ 的距离就相当于 $\text{dep}$，所以就可以得到：

$2\times(\text{dep}(x)-\text{dep}(y))\equiv 0\pmod{d}$

通过瞪眼法可以得到方程的解为 $\text{dep}(x)=\text{dep}(y)$，或者 $2\mid d$ 且 $\text{dep}(x)-\text{dep}(y)\mid \frac{d}{2}$。

当然，在最后计算答案的时候需要满足 $\text{dep}(x)\equiv k\pmod d$。

时间复杂度 $O(n)$，做完了。