配点 : $600$ 点

問題文

$N$ 頂点からなる無向木が与えられます。 頂点を順に頂点 $1$, 頂点 $2$, $\ldots$, 頂点 $N$ とすると、 $1\leq i\leq N-1$ について、$i$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。 また、それぞれの頂点には正整数が割り当てられており、 具体的には頂点 $i$ には $A_i$ が割り当てられています。

相異なる $2$ 頂点 $s$, $t$ 間のコスト $C(s,t)$ が次のようにして定められます。

頂点 $s$ と頂点 $t$ を結ぶ単純パス上の頂点を順に $p_1(=s)$, $p_2$, $\ldots$, $p_k(=t)$ とする。 ここで、$k$ はパス上の(端点含む)頂点数である。 このとき、$C(s,t)=k\times \gcd (A_{p_1},A_{p_2},\ldots,A_{p_k})$ で定める。 ただし、$\gcd (X_1,X_2,\ldots, X_k)$ で $X_1,X_2,\ldots, X_k$ の最大公約数を表す。

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j)$ を $998244353$ で割ったあまりを求めてください。

制約

• $2 \leq N \leq 10^5$
• $1 \leq A_i\leq 10^5$
• $1\leq U_i
• 入力は全て整数である。
• 与えられるグラフは木である。

入力

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

$N$

$A_1$ $A_2$ $\cdots$ $A_N$

$U_1$ $V_1$

$U_2$ $V_2$

$\vdots$

$U_{N-1}$ $V_{N-1}$

出力

$\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j)$ を $998244353$ で割ったあまりを出力せよ。

4
24 30 28 7
1 2
1 3
3 4

47

頂点 $1$ と頂点 $2$ 、頂点 $1$ と頂点 $3$ 、頂点 $3$ と頂点 $4$ がそれぞれ直接辺で結ばれています。 よって、コストはそれぞれ次のように求められます。

• $C(1,2)=2\times \gcd(24,30)=12$
• $C(1,3)=2\times \gcd(24,28)=8$
• $C(1,4)=3\times \gcd(24,28,7)=3$
• $C(2,3)=3\times \gcd(30,24,28)=6$
• $C(2,4)=4\times \gcd(30,24,28,7)=4$
• $C(3,4)=2\times \gcd(28,7)=14$

求める値は $\displaystyle\sum_{i=1}^{3}\sum_{j=i+1}^4 C(i,j)=(12+8+3)+(6+4)+14=47$ を $998244353$ で割ったあまりの $47$ となります。

10
180 168 120 144 192 200 198 160 156 150
1 2
2 3
2 4
2 5
5 6
4 7
7 8
7 9
9 10

1184