树上的 GCD 代价

题目描述

给定一棵有 $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$ 取模。

输入格式

输入按以下格式从标准输入给出：

N
A_1 A_2 … A_N
U_1 V_1
U_2 V_2
⋮
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

数据范围

• $2 \leq N \leq 10^5$
• $1 \leq A_i\leq 10^5$
• $1\leq U_i \lt V_i\leq N$
• 输入中的所有值都是整数。
• 给定的图是一棵树。