题目描述

$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$ で割ったあまりを求めてください。

输入格式

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

$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$ で割ったあまりを出力せよ。

题目大意

题目描述

给定一颗树有 $n$ 个结点，每个结点上有一个权值 $a_i$, 对于每条至少包含两个点的简单路径，它的贡献为 路径上点的数量(包括端点)$\times$路径上所有点的 $a_i$ 的最大公约数(gcd)。
求所有简单路径的贡献之和，对 $998244353$ 取模。

输入格式

第一行输入 $n$，随后一行 $n$ 个正整数$a_i$ 。
然后 $n-1$ 行每行一条边 $(u_i,v_i)$ 表示这棵树。

输出格式

输出答案所求，$\bmod \ 998244353$ 。

样例解释 #1

记 $C(i,j)$ 表示从 $i$ 到 $j$ 的路径的贡献。
$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$.

数据范围

$2 \le n \le 10^5$
$1 \le a_i \le 10^5$

4
24 30 28 7
1 2
1 3
3 4

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

提示

制約

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

Sample Explanation 1

頂点 $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$ となります。