## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ to $N$. Factory $i$ has an electrical coefficient of ${A}_{i}$. There are also $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\left(x,y,z\right)$ 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\left(x,y,z\right)$ as the number of distinct prime factors of $\text{GCD}\left({A}_{x},{A}_{y},{A}_{z}\right)$.

To measure the electrical efficiency, you must find the sum of $f\left(x,y,z\right)×g\left(x,y,z\right)$ for all combinations of $\left(x,y,z\right)$ such that $1\le x. Because the answer can be very large, you just need to output the answer modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.

Note: $\text{GCD}\left({k}_{1},{k}_{2},{k}_{3}\right)$ is the greatest common divisor of ${k}_{1}$${k}_{2}$, and ${k}_{3}$, which is the biggest integer that simultaneously divides ${k}_{1}$${k}_{2}$, and ${k}_{3}$.

Input

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

Solution Click Below:-  👉
👇👇👇👇👇

The second line contains $N$ integers ${A}_{1},{A}_{2},\dots ,{A}_{N}$ ($1\le {A}_{i}\le 2\cdot {10}^{5}$) — the electrical coefficients of the factories.

The $j$-th of the next $N-1$ lines contains two integers ${U}_{j}$ and ${V}_{j}$ ($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\left(x,y,z\right)×g\left(x,y,z\right)$ for all combinations of $\left(x,y,z\right)$ such that $1\le x, modulo $998\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$