GCD cost on the tree

题目描述

你被给定了一个有 $N$ 个顶点的无向树。
我们将顶点称为顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$。对于每个 $1\leq i\leq N-1$，第 $i$ 条边连接顶点 $U_i$ 和顶点 $V_i$。
此外，每个顶点被赋予一个正整数：顶点 $i$ 的赋值为 $A_i$。 两个不同顶点 $s$ 和 $t$ 之间的代价 $C(s,t)$ 定义如下。

令 $p_1(=s)$、$p_2$、$\ldots$、$p_k(=t)$ 为连接顶点 $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$ 取模。

输入格式

输入从标准输入按以下格式给出： $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

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<V_i\leq N 输入中的所有值均为整数。 给定的图是树。存在直接连接顶点 $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$.

标签: AtCoder|abc248G

来源

AtCoder|abc248G