[Solution] Electrical Efficiency Codeforces Solution

E. Electrical Efficiency

time limit per test

3 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

In the country of Dengkleknesia, there are 𝑁$N$ factories numbered from 1$1$ to 𝑁$N$. Factory 𝑖$i$ has an electrical coefficient of 𝐴𝑖$A_i$. There are also 𝑁−1$N-1$ power lines with the 𝑗$j$-th power line connecting factory 𝑈𝑗$U_j$ and factory 𝑉𝑗$V_j$. It can be guaranteed that each factory in Dengkleknesia is connected to all other factories in Dengkleknesia through one or more power lines. In other words, the collection of factories forms a tree. Each pair of different factories in Dengkleknesia can use one or more existing power lines to transfer electricity to each other. However, each power line needs to be turned on first so that electricity can pass through it.

Define 𝑓(𝑥,𝑦,𝑧)$f(x,y,z)$ as the minimum number of power lines that need to be turned on so that factory 𝑥$x$ can make electrical transfers to factory 𝑦$y$ and factory 𝑧$z$. Also define 𝑔(𝑥,𝑦,𝑧)$g(x,y,z)$ as the number of distinct prime factors of GCD(𝐴𝑥,𝐴𝑦,𝐴𝑧)$\text{GCD}(A_x,A_y,A_z)$.

To measure the electrical efficiency, you must find the sum of 𝑓(𝑥,𝑦,𝑧)×𝑔(𝑥,𝑦,𝑧)$f(x,y,z)\times g(x,y,z)$ for all combinations of (𝑥,𝑦,𝑧)$(x,y,z)$ such that 1≤𝑥<𝑦<𝑧≤𝑁$1\le x<y<z\le N$. Because the answer can be very large, you just need to output the answer modulo 998244353$998244353$.

Note: GCD(𝑘1,𝑘2,𝑘3)$\text{GCD}(k_1,k_2,k_3)$ is the greatest common divisor of 𝑘1$k_1$, 𝑘2$k_2$, and 𝑘3$k_3$, which is the biggest integer that simultaneously divides 𝑘1$k_1$, 𝑘2$k_2$, and 𝑘3$k_3$.

Input

The first line contains a single integer 𝑁$N$ (1≤𝑁≤2⋅105$1\le N\le 2\cdot {10}^5$) — the number of factories in Dengkleknesia.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

The second line contains 𝑁$N$ integers 𝐴1,𝐴2,…,𝐴𝑁$A_1,A_2,\dots ,A_N$ (1≤𝐴𝑖≤2⋅105$1\le A_i\le 2\cdot {10}^5$) — the electrical coefficients of the factories.

The 𝑗$j$-th of the next 𝑁−1$N-1$ lines contains two integers 𝑈𝑗$U_j$ and 𝑉𝑗$V_j$ (1≤𝑈𝑗,𝑉𝑗≤𝑁$1\le U_j,V_j\le N$) — a power line that connects cities 𝑈𝑗$U_j$ and 𝑉𝑗$V_j$. The collection of factories forms a tree.

Output

An integer representing the sum of 𝑓(𝑥,𝑦,𝑧)×𝑔(𝑥,𝑦,𝑧)$f(x,y,z)\times g(x,y,z)$ for all combinations of (𝑥,𝑦,𝑧)$(x,y,z)$ such that 1≤𝑥<𝑦<𝑧≤𝑁$1\le x<y<z\le N$, modulo 998244353$998244353$

$\mathrm{<br>}$