CF1725E.Electrical Efficiency

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(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 $\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 \leq x \lt y \lt z \leq N$. Because the answer can be very large, you just need to output the answer modulo $998\,244\,353$.

Note: $\text{GCD}(k_1, k_2, k_3)$ 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$.

在邓克勒克尼西亚国，共有 $N$ 座工厂，编号从 $1$ 到 $N$。工厂 $i$ 具有电学系数 $A_i$。此外还有 $N-1$ 条输电线路，其中第 $j$ 条输电线路连接工厂 $U_j$ 与工厂 $V_j$。可以保证邓克勒克尼西亚的所有工厂通过一条或多条输电线路彼此连通。换言之，这些工厂构成一棵树。邓克勒克尼西亚中任意两个不同的工厂均可借助一条或多条现有输电线路相互传输电力。但每条输电线路必须先被开启，电力才能通过。

定义 $f(x, y, z)$ 为：使工厂 $x$ 能够向工厂 $y$ 和工厂 $z$ 同时传输电力所需开启的最少输电线路数量。
定义 $g(x, y, z)$ 为 $\text{GCD}(A_x, A_y, A_z)$ 的不同质因数的个数。

为衡量电力传输效率，你需要计算所有满足 $1 \leq x \lt y \lt z \leq N$ 的三元组 $(x, y, z)$ 对应的 $f(x, y, z) \times g(x, y, z)$ 的总和。由于答案可能非常大，你只需输出该总和对 $998\,244\,353$ 取模的结果。

注：$\text{GCD}(k_1, k_2, k_3)$ 表示 $k_1$、$k_2$ 和 $k_3$ 的最大公约数，即能同时整除 $k_1$、$k_2$ 和 $k_3$ 的最大整数。

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

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ ($1 \leq A_i \leq 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.

第一行包含一个整数 $N$（$1 \le N \le 2 \cdot 10^5$）—— 表示登克勒克内西亚的工厂数量。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$（$1 \leq A_i \leq 2 \cdot 10^5$）—— 表示各工厂的电学系数。

接下来的 $N-1$ 行中，第 $j$ 行包含两个整数 $U_j$ 和 $V_j$（$1 \le U_j, V_j \le N$）—— 表示一条连接城市 $U_j$ 与 $V_j$ 的输电线路。这些工厂构成一棵树。

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 \leq x \lt y \lt z \leq N$, modulo $998\,244\,353$

一个整数，表示对所有满足 $1 \leq x \lt y \lt z \leq N$ 的三元组 $(x, y, z)$，$f(x, y, z) \times g(x, y, z)$ 的和，结果对 $998\,244\,353$ 取模。

In the first example, the only $(x, y, z)$ possible is $(1, 2, 3)$. Because $\text{GCD}(A_1, A_2, A_3) = \text{GCD}(1, 2, 3) = 1$ has $0$ distinct prime factors, therefore $f(x, y, z) \times g(x, y, z) = 2 \times 0 = 0$.

In the second example, all triples $(x, y, z)$ that satisfy the condition are as follows:

• $(1, 2, 3) \rightarrow f(1, 2, 3) \times g(1, 2, 3) = 2 \times 1 = 2$
• $(1, 2, 4) \rightarrow f(1, 2, 4) \times g(1, 2, 4) = 2 \times 1 = 2$
• $(1, 3, 4) \rightarrow f(1, 3, 4) \times g(1, 3, 4) = 3 \times 2 = 6$
• $(2, 3, 4) \rightarrow f(2, 3, 4) \times g(2, 3, 4) = 2 \times 1 = 2$

So the electrical efficiency is $2 + 2 + 6 + 2 = 12$.

在第一个例子中，唯一可能的 $(x, y, z)$ 是 $(1, 2, 3)$。由于 $\text{GCD}(A_1, A_2, A_3) = \text{GCD}(1, 2, 3) = 1$ 有 $0$ 个不同的质因数，因此 $f(x, y, z) \times g(x, y, z) = 2 \times 0 = 0$。

在第二个例子中，所有满足条件的三元组 $(x, y, z)$ 如下：

• $(1, 2, 3) \rightarrow f(1, 2, 3) \times g(1, 2, 3) = 2 \times 1 = 2$
• $(1, 2, 4) \rightarrow f(1, 2, 4) \times g(1, 2, 4) = 2 \times 1 = 2$
• $(1, 3, 4) \rightarrow f(1, 3, 4) \times g(1, 3, 4) = 3 \times 2 = 6$
• $(2, 3, 4) \rightarrow f(2, 3, 4) \times g(2, 3, 4) = 2 \times 1 = 2$

因此，电效率为 $2 + 2 + 6 + 2 = 12$。