GCD cost on the tree

AtCoder

IDabc248_g

Time8000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

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

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

Output #2

API Response (JSON)

{
  "problem": {
    "name": "GCD cost on the tree",
    "description": {
      "content": "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 Vert",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc248_g"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an undirected tree with $N$ vertices.  \nLet 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 Vert...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments