Coprime Path

解説

この問題は各頂点を根とした根付き木それぞれについて、累積 $\mathrm{gcd}$ を持ちながら DFS をすることで全体で $O(N^2 \ \mathrm{log} A)$ で解くことができます（$A = \mathrm{max}\{A_i\}$ とします）。計算量解析の詳細は後述します。なお、この問題は HL 分解でも解くことができます。

まずは愚直解をベースに考察をしてみましょう。頂点の組 $(L, R)$ を指定して、頂点 $L$ から頂点 $R$ への最短パス $\{ L, \ldots , R \}$ を求めることができれば、頂点の組 $(L, R)$ を全探索することで答えを計算することができます。

• 最短パス $\{ L, \ldots , R \}$ が効率良く求まったと仮定して、答えを求めるパートの計算量はどうなるでしょうか？　最短パス $\{ L, \ldots , R \}$ の頂点数を $f(L, R)$ とおき、$\mathrm{gcd}(A_L, \ldots , A_R)$ の計算量が最悪ケースで $O(f(L, R) + \mathrm{log} A)$ になることに注意すれば、求める計算量は $O(\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} (f(L, R) + \mathrm{log} A))$ になります。最悪ケースとして木がパスグラフである場合を考えると $O(N^3 + N^2 \ \mathrm{log} A)$ となるため（導出は読者への課題とします）、愚直解では間に合わないことが分かります。

• 最短パス $\{ L, \ldots , R \}$ はどのように求めたらいいでしょうか？　頂点の組 $(L, R)$ ごとに DFS で愚直に計算することはできますが、これでは計算量が最悪ケースで $O(N)$ になり、全体では前述のパスグラフの場合で最悪 $O(N^3)$ の計算量となるため間に合いません。適当に根を決めて根からのパスを DFS で前計算しておき LCA を用いて効率よく構築することは可能ですが、パスグラフの場合に「パスに登場する頂点数」の総和のオーダーが $O(N^3)$ になってしまうため間に合いません。

これらのことを踏まえると、頂点の組 $(L, R)$ を指定して最短パス $\{ L, \ldots , R \}$ を毎回独立に求める方法にはかなりの無駄が生じていることが分かります（それぞれのパスには共通部分が数多く存在しているためです）。よって、その共通部分を使い回すことで効率よく計算できないかを考えることが本問の重要なポイントになります。

やや天下り的ですが、これには DFS がぴったりハマります。頂点 $x$ を根とする根付き木を DFS することを考えると、$L = x$ であるような頂点の組 $(L, R)$ の最短パス $\{ L, \ldots , R \}$ を $O(N)$ で全て列挙することができます。$\mathrm{gcd}$ についても DFS をしながら累積計算をすることで効率よく求められます。

ところで、制約を確認してみると $N \leq 1000$ となっていることから、$\mathrm{gcd}$ の計算パートはパスごとに最悪 $O(\mathrm{log} A)$ の計算量がかかるとして見積もれば、「頂点 $L$ を根とする根付き木の DFS」を $L$ について全探索することで全体で $O(N^2 \ \mathrm{log} A)$ で解くことができます。

計算量解析

一般に、最大公約数 $\mathrm{gcd}(a, b)$ はユークリッドの互除法によって $O(\mathrm{log}(\mathrm{min}(a, b)))$ で計算できます（最悪ケースは $a, b$ がフィボナッチ数列の隣接 $2$ 項であるとき）。では $N$ 個の整数 $\{ A_i \}$ の最大公約数の計算量はどうなるでしょうか？　愚直に見積もれば $O(N \ \mathrm{log} A)$ となりますが（$A = \mathrm{max}\{A_i\}$ とします）、ユークリッドの互除法の計算ステップ回数をよく考えると $O(N + \mathrm{log} A)$ に抑えられることが分かります。

本問の場合、各頂点を根とした根付き木それぞれについて、DFS をしながら累積的に $\mathrm{gcd}$ を計算するため、全体計算量の上界を適切に解析することは難しくなります。しかし、定数倍 $1/8$ は付くものの $O(N^2 \ \mathrm{log} A)$ のテストケースは下記のように構築することができます。

• スターグラフを作り、$(N - 1)$ 個の葉を半数ずつのグループ A, B に分ける
• フィボナッチ数列の隣接 $2$ 項であって $\sqrt{A}$ 程度のものを選ぶ
  • $(10946, 17711), (17711, 28657)$ など
• 隣接 $2$ 項の一方をグループ A の葉に、もう一方をグループ B の葉にそれぞれ配置する
• 中央ノードに隣接 $2$ 項の最小公倍数を配置する
  • 例えば、$\mathrm{lcm}(17711, 28657) = 507544127 < 10^9$
• 以上により、$\mathrm{gcd}$ の計算ステップ回数が $\mathrm{log}\sqrt{A}$ 程度となるパスが、グループ A の葉とグループ B の葉のペアの個数（$\simeq N/2 \times N/2$）の分だけ存在するため、全体では $O(N^2 \ \mathrm{log} A)$ の計算量となるテストケースを構築することができます。

$O(N^2 \ \mathrm{log} A)$ のテストケースの構築に関する具体案及びその計算量解析は tester の MMNMM さんの指摘によるものです。ありがとうございます。

解答例