分数: 600 点
问题陈述
给你一棵无向树 N 顶点。
让我们将顶点称为 Vertex 1,顶点 2, \ldots,顶点 N。对于每个 1\leq i\leq N-1, i第一条边连接顶点 U_i 和顶点 V_i.
此外,每个顶点都分配有一个正整数: Vertex i 已分配 A_i.
两个不同顶点之间的成本 s 和 t, C(s,t)定义如下。
让 p_1(=s), p_2, \ldots, p_k(=t) 是连接 Vertex 的简单路径的顶点 s 和顶点 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.
样本输入 1
4 24 30 28 7 1 2 1 3 3 4
示例输出 1
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.
示例输入 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