102486: [AtCoder]ABC248 G - GCD cost on the tree

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

You are given an undirected tree with $N$ vertices.
Let us call the vertices Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$. For each $1\leq i\leq N-1$, the $i$-th edge connects Vertex $U_i$ and Vertex $V_i$.
Additionally, each vertex is assigned a positive integer: Vertex $i$ is assigned $A_i$.

The cost between two distinct vertices $s$ and $t$, $C(s,t)$, is defined as follows.

Let $p_1(=s)$, $p_2$, $\ldots$, $p_k(=t)$ be the vertices of the simple path connecting Vertex $s$ and Vertex $t$, where $k$ is the number of vertices in the path (including the endpoints).
Then, let $C(s,t)=k\times \gcd (A_{p_1},A_{p_2},\ldots,A_{p_k})$,
where $\gcd (X_1,X_2,\ldots, X_k)$ denotes the greatest common divisor of $X_1,X_2,\ldots, X_k$.

Find $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j)$, modulo $998244353$.

Constraints

  • $2 \leq N \leq 10^5$
  • $1 \leq A_i\leq 10^5$
  • $1\leq U_i<V_i\leq N$
  • All values in input are integers.
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

Output

Print $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j)$, modulo $998244353$.


Sample Input 1

4
24 30 28 7
1 2
1 3
3 4

Sample Output 1

47

There are edges directly connecting Vertex $1$ and $2$, Vertex $1$ and $3$, and Vertex $3$ and $4$. Thus, the costs are computed as follows.

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

Thus, the sought value is $\displaystyle\sum_{i=1}^{3}\sum_{j=i+1}^4 C(i,j)=(12+8+3)+(6+4)+14=47$ modulo $998244353$, which is $47$.


Sample Input 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

Sample Output 2

1184

Input

题意翻译

#### 题目描述 给定一颗树有 $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$. #### 数据范围 $2 \le n \le 10^5$ $1 \le a_i \le 10^5$

Output

得分:600分

问题描述

给你一个无向树,它有N个顶点。

我们将顶点称为顶点1,顶点2,…,顶点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$,…,$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取模。

约束条件

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

加入题单

上一题 下一题 算法标签: