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$.

输入输出样例 #1

输入 #1

4
24 30 28 7
1 2
1 3
3 4

输出 #1

47

输入输出样例 #2

输入 #2

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

输出 #2

1184

说明/提示

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