配点 : 400400

問題文

NN 頂点からなる木が与えられます。ii 番目の辺は頂点 uiu_i と頂点 viv_i を繋いでいます。また、ii 番目の頂点には正の整数 AiA_i が書かれています。

パス {v1,,vn}\{ v_1, \ldots , v_n \} が次の条件を満たすとき、そのパスは Coprime Path であると定義します。

  • gcd(v1,,vn)=1\mathrm{gcd}(v_1, \ldots , v_n) = 1

頂点の組 (L,R) (1L<RN)(L, R) \ (1 \leq L < R \leq N) のうち、頂点 LL から頂点 RR への最短パス {L,,R}\{ L, \ldots , R \}Coprime Path であるものの個数を求めてください。

ただし、gcd(a1,,an)\mathrm{gcd}(a_1, \ldots , a_n){a1,,an}\{ a_1, \ldots , a_n \} の最大公約数を表します。

制約

  • 1N10001 \leq N \leq 1000
  • 1ui,viN1 \leq u_i, v_i \leq N
  • 1Ai1091 \leq A_i \leq 10^9
  • 与えられるグラフは木である
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

NN
A1 A2  ANA_1 \ A_2 \ \cdots \ A_N
u1 v1u_1 \ v_1
u2 v2u_2 \ v_2
\vdots
uN1 vN1u_{N-1} \ v_{N-1}

出力

頂点の組 (L,R) (1L<RN)(L, R) \ (1 \leq L < R \leq N) のうち、頂点 LL から頂点 RR への最短パス {L,,R}\{ L, \ldots , R \}Coprime Path であるものの個数を出力してください。

サンプル 1

入力1
3
1 2 3
1 2
1 3
出力1
3

頂点の組 (L,R)(L, R) として次の 33 通りがあります。

  • (L,R)=(1,2)(L, R) = (1, 2) のとき、gcd(A1,A2)=gcd(1,2)=1\mathrm{gcd}(A_1, A_2) = \mathrm{gcd}(1, 2) = 1
  • (L,R)=(1,3)(L, R) = (1, 3) のとき、gcd(A1,A3)=gcd(1,3)=1\mathrm{gcd}(A_1, A_3) = \mathrm{gcd}(1, 3) = 1
  • (L,R)=(2,3)(L, R) = (2, 3) のとき、gcd(A2,A1,A3)=gcd(2,1,3)=1\mathrm{gcd}(A_2, A_1, A_3) = \mathrm{gcd}(2, 1, 3) = 1

このうち、gcd\mathrm{gcd}11 となる頂点の組は 33 つあります。よって、答えは 33 です。

サンプル 2

入力2
5
6 2 3 4 1
1 2
1 3
1 4
4 5
出力2
6

頂点の組 (L,R)(L, R) として次の 1010 通りがあります。

  • (L,R)=(1,2)(L, R) = (1, 2) のとき、gcd(A1,A2)=gcd(6,2)=2\mathrm{gcd}(A_1, A_2) = \mathrm{gcd}(6, 2) = 2
  • (L,R)=(1,3)(L, R) = (1, 3) のとき、gcd(A1,A3)=gcd(6,3)=3\mathrm{gcd}(A_1, A_3) = \mathrm{gcd}(6, 3) = 3
  • (L,R)=(1,4)(L, R) = (1, 4) のとき、gcd(A1,A4)=gcd(6,4)=2\mathrm{gcd}(A_1, A_4) = \mathrm{gcd}(6, 4) = 2
  • (L,R)=(1,5)(L, R) = (1, 5) のとき、gcd(A1,A4,A5)=gcd(6,4,1)=1\mathrm{gcd}(A_1, A_4, A_5) = \mathrm{gcd}(6, 4, 1) = 1
  • (L,R)=(2,3)(L, R) = (2, 3) のとき、gcd(A2,A1,A3)=gcd(2,6,3)=1\mathrm{gcd}(A_2, A_1, A_3) = \mathrm{gcd}(2, 6, 3) = 1
  • (L,R)=(2,4)(L, R) = (2, 4) のとき、gcd(A2,A1,A4)=gcd(2,6,4)=2\mathrm{gcd}(A_2, A_1, A_4) = \mathrm{gcd}(2, 6, 4) = 2
  • (L,R)=(2,5)(L, R) = (2, 5) のとき、gcd(A2,A1,A4,A5)=gcd(2,6,4,1)=1\mathrm{gcd}(A_2, A_1, A_4, A_5) = \mathrm{gcd}(2, 6, 4, 1) = 1
  • (L,R)=(3,4)(L, R) = (3, 4) のとき、gcd(A3,A1,A4)=gcd(3,6,4)=1\mathrm{gcd}(A_3, A_1, A_4) = \mathrm{gcd}(3, 6, 4) = 1
  • (L,R)=(3,5)(L, R) = (3, 5) のとき、gcd(A3,A1,A4,A5)=gcd(3,6,4,1)=1\mathrm{gcd}(A_3, A_1, A_4, A_5) = \mathrm{gcd}(3, 6, 4, 1) = 1
  • (L,R)=(4,5)(L, R) = (4, 5) のとき、gcd(A4,A5)=gcd(4,1)=1\mathrm{gcd}(A_4, A_5) = \mathrm{gcd}(4, 1) = 1

このうち、gcd\mathrm{gcd}11 となる頂点の組は 66 つあります。よって、答えは 66 です。

サンプル 3

入力3
10
3 1 4 1 5 9 2 6 5 3
1 2
1 3
1 8
3 4
3 5
5 6
5 7
8 9
8 10
出力3
42

提出


Go (1.21)