题目描述

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