CF2002D2 DFS Checker

有结论,如果 fa(dfni+1)fa(dfn_{i+1})dfnidfn_i 的祖先,那么满足 dfndfn 是合法的,做完了。

CF1835D Doctor's Brown Hypothesis

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

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

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

假设图中所有的环的长度为 len1,len2,,lenmlen_1,len_2,\cdots,len_m,那么记 d=gcdi=1mlenid=\gcd\limits_{i=1}^m len_i

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

在下的 SCC 中有一些性质:

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

证明:

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

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

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

证明:

假设 aa 在长度为 xx 的环上,而 bb 不在。

假设 aba\to b 的路径长度为 ww,那么根据上面的性质,显然 bab\to a 的长度就是 ww

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

换而言之:

xyx\to y 的一条复杂路径可以表示为 xyx\to y 的简单路径的长度加上 i=1mai×leni\sum\limits_{i=1}^m a_i\times len_i,其中 aiN\forall a_i\in \mathbb{N}

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

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

证明:

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

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

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

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

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

gcd(a,b)=g\gcd(a,b)=g,那么 a=ag×ga=\dfrac{a}{g}\times gb=bg×gb=\dfrac{b}{g}\times g,所以就有 a+b=g×(ag+bg)a+b=g\times ({\dfrac{a}{g}+\dfrac{b}{g}})

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

回到这个题目的具体要求,假设 xyx\to y 的简单路径长度为 LenLen,那么题目的要求就是:

Len+i=1mai×lenik(modd)Len+\sum\limits_{i=1}^m a_i\times len_i\equiv k \pmod{d}

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

因为 xyx\to y 的长度和 yxy\to x 的长度需要一样,所以我们先考虑判断 dis(xy)dis(yx)(modd)\text{dis}(x\to y)\equiv \text{dis}(y\to x)\pmod d

因为第三个性质,所以不妨我们直接让 xx 走到 rtrt 然后再走到 yy,反之同理。

因为 xyx\to y 的边权为 ww 那么 yxy\to x 的边权就为 w-w,所以就相当于判断:

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

因为 xxyyrtrt 的距离就相当于 dep\text{dep},所以就可以得到:

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

通过瞪眼法可以得到方程的解为 dep(x)=dep(y)\text{dep}(x)=\text{dep}(y),或者 2d2\mid ddep(x)dep(y)d2\text{dep}(x)-\text{dep}(y)\mid \dfrac{d}{2}

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

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