G - 树上的最大公约数代价

得分：$600$ 分

题目描述

给定一个无向树，有 $N$ 个节点。
将这些节点分别命名为结点 $1$，结点 $2$，$\ldots$，结点 $N$。对于 $1\leq i\leq N-1$，第 $i$ 条边连接了结点 $U_i$ 和结点 $V_i$。
此外，每个节点都被赋予了一个正整数：结点 $i$ 被赋予了 $A_i$。

两个不同节点 $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<V_i\leq N$
• 输入中的所有数都是整数。
• 给定的图是一棵树。

输入

从标准输入读入输入的格式如下：

$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