有结论,如果 fa(dfni+1) 是 dfni 的祖先,那么满足 dfn 是合法的,做完了。
一个实现不太一样的做法。
因为需要分别存在 x→y 和 y→x 的路径,所以满足题目要求的 (x,y) 肯定是在一个 SCC 中的。
对于每一个 SCC 分开考虑,最后将结果相加即可,下面讨论的图都是强连通的。
假设图中所有的环的长度为 len1,len2,⋯,lenm,那么记 d=i=1gcdmleni。
下面讨论的图都是在在对 d 取模意义 下的。
在下的 SCC 中有一些性质:
如果存在一条路径 a→b,而且边权为 w,那么就可以构造出 b→a 而且边权为 −w 的路径。
证明:
因为 a,b 在同一个强连通分量内,所以它们必然在一个环中,假设这个环的边权和为 s。那么从 b 出发绕着环走 t 圈,这样的贡献就是 s×t 也就是 0。
所以只要在最后一圈的时候直接停在 a 那么就相当于构造出了一条 b→a 的边权为 −w 的路径。
另外有一个性质,如果强连通分量上有一个环,那么所有的点都可以看作在这个环上。
证明:
假设 a 在长度为 x 的环上,而 b 不在。
假设 a→b 的路径长度为 w,那么根据上面的性质,显然 b→a 的长度就是 w。
那么就可以构造 b→a→b 的路径,在到达 a 之后可以随意的在环上行走,而结束后又可以原路返回。容易理解,这样路径的长度为 w+x+(−w)=x。
换而言之:
x→y 的一条复杂路径可以表示为 x→y 的简单路径的长度加上 i=1∑mai×leni,其中 ∀ai∈N。
这样就解决有些 ai=0 但是却经过了一些其他必须要经过 i 的环才能到达的环的问题。
最后还有一个性质,如果有一条 x→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=ga×g,b=gb×g,所以就有 a+b=g×(ga+gb)。
于是就遍历这个 dfs 树,如果遇到了返祖边那么就更新 gcd。
回到这个题目的具体要求,假设 x→y 的简单路径长度为 Len,那么题目的要求就是:
Len+i=1∑mai×leni≡k(modd)
因为 ∀i∈[1,m]∩Z 都满足 d∣leni,所以 i=1∑mai×leni≡0modd,也就得到了其实题目的要求是 Len≡k。
因为 x→y 的长度和 y→x 的长度需要一样,所以我们先考虑判断 dis(x→y)≡dis(y→x)(modd)。
因为第三个性质,所以不妨我们直接让 x 走到 rt 然后再走到 y,反之同理。
因为 x→y 的边权为 w 那么 y→x 的边权就为 −w,所以就相当于判断:
−dis(rt,x)+dis(rt,y)≡dis(rt,x)−dis(rt,y)(modd)
因为 x 和 y 到 rt 的距离就相当于 dep,所以就可以得到:
2×(dep(x)−dep(y))≡0(modd)
通过瞪眼法可以得到方程的解为 dep(x)=dep(y),或者 2∣d 且 dep(x)−dep(y)∣2d。
当然,在最后计算答案的时候需要满足 dep(x)≡k(modd)。
时间复杂度 O(n),做完了。