AT_abc248_g [ABC248G] GCD cost on the tree

给定一颗树有 $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$