题目是 AT_abc306_g [ABC306G] Return to 1 – 洛谷。

以下所有叙述均不考虑自环、重边。

上题本质上要求求出所有经过点 $1$ 的环环长的 gcd。

首先把包含点 $1$ 的强连通分量拿出来，显然只用考虑这个子图即可。

接下来考虑以 $1$ 为根建立任意一棵 dfs 搜索树，我们不加证明地给出一个断言：答案等于 $\gcd |\text{dep}_{u_i}-\text{dep}_{v_i}+1|$，其中 $\text{dep}$ 表示在 dfs 搜索树中的深度，$u_i\to v_i$ 表示当前强连通分量中的每条边。

下面我们来证明这个断言。

显然对于搜索树上的每条边 $\text{dep}_{u_i}-\text{dep}_{v_i}+1=0$，所以只用考虑所有返祖边即可。

我们定义主元为：强连通分量中的某个环，满足这个环在搜索树上恰好对应一条根到叶子的链，显然他对应的 $|\text{dep}_{u_i}-\text{dep}_{v_i}+1|$ 就是环长。

可以有多个主元，我们对每个环 $i$，设他在图中对应的点集和边集分别是 $S_i,E_i$，显然主元之间满足 $S_i\cap S_j=\{1\},E_i\cap E_j=\varnothing$。

对于原图的任意一个非主元的环 $j$，我们找到一个主元 $i$ 满足 $\{1\}\subset S_i\cap S_j$。

我们设 $T=E_j\cap E_i$，接下来我们先只考虑 $T$ 中的边在搜索树上可以表示为至多两条祖先到后代的链的情况，形如下图：

粉色代表搜索树上的边

上图中环是 $1\to2\to4\to5\to1$，对应的主元是 $1\to2\to3\to4\to5\to1$，他们的边集的交是 $1\to2,4\to5$，显然构成两条搜索树上祖先到后代的链。

不难发现，上述条件（称为条件 1）的另一个等价形式是，$E_j$ 中有且只有两条边不在搜索树上（$2\to4$ 和 $5\to1$），且一条边必定已经被主元考虑过（$5\to1$），这代表着环 $j$ 对答案的贡献必定在 $2\to4$ 这条边上算到，那么考虑此时 $|\text{dep}_{u_i}-\text{dep}_{v_i}+1|=dep_{v_i}-dep_{u_i}-1$，由于其他的地方两个环是重合的，所以 $dep_{v_i}-dep_{u_i}-1$ 恰好可以表示两个环的环长之差。

又 $\gcd(a,b)=\gcd(a,a-b)$，所以环 $j$ 的贡献也被我们正确的计算了。

那么考虑所有不符合条件 1 的环，即下图中的环 $1\to2\to3\to5\to6\to7\to9\to1$：

那么考虑 $E_j$ 和对应主元的 $E_i$ 交集构成了搜索树上的不知道多少条链，且这些链不交，均分布于某一个叶子的根链上，那么他和对应主元的环长度差可以写成 $c_1+c_2+\cdots$ 的形式，其中 $c_i$ 是相邻两个链之间隔开的边数，容易发现，$c_1,c_2\cdots$ 每个数都会在一个符合条件 1 的环上被算到，由于 $\gcd(a+b+c,a,b)=\gcd(a,b)$，所以这样的环同样也被正确的计算了。

所以我们证明了我们的结论。