Electrical Efficiency

题意翻译

树上 $n$ 个点，每个点有点权 $a_i$。对于一个三元组 $(x,y,z)$ 满足 $1 \leq x < y < z \leq n$，定义 $f(x,y,z)$ 为树上连通这三个点的连通块的最小边数（即三个点两两间路径的并的边数），$g(x,y,z)$ 为 $\gcd(a_x,a_y,a_z)$ 所含的不同质因子个数，求 $\sum f(x,y,z)\times g(x,y,z)$，对 998244353 取模。 $n,a_i \leq 2 \times 10^5$。

题目描述

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

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

3
1 2 3
1 2
2 3

输出样例 #1

0

输入样例 #2

4
6 14 6 6
1 2
2 3
2 4

输出样例 #2

12

说明

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

**题意翻译**

在Dengkleknesia国家有 $ N $ 个工厂，编号从 $ 1 $ 到 $ N $。工厂 $ i $ 有一个电力系数 $ A_i $。还有 $ N-1 $ 条电线，第 $ j $ 条电线连接工厂 $ U_j $ 和工厂 $ V_j $。可以保证Dengkleknesia的每个工厂都通过一条或多条电线与Dengkleknesia的其他工厂相连。换句话说，工厂的集合形成了一棵树。Dengkleknesia的每对不同的工厂可以使用一条或多条现有的电线来相互传输电力。但是，每条电线都需要先打开，电力才能通过。

定义 $ f(x, y, z) $ 为需要打开的最少电线数，以便工厂 $ x $ 可以对工厂 $ y $ 和工厂 $ z $ 进行电力传输。同时定义 $ g(x, y, z) $ 为 $ \text{GCD}(A_x, A_y, A_z) $ 的不同质因子数量。

为了衡量电力效率，你必须找到所有满足 $ 1 \leq x < y < 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 $ 的最大整数。

**输入输出格式**

**输入格式**
- 第一行包含一个整数 $ N $ ( $ 1 \le N \le 2 \cdot 10^5 $ ) — Dengkleknesia的工厂数量。
- 第二行包含 $ N $ 个整数 $ A_1, A_2, \dots, A_N $ ( $ 1 \leq A_i \leq 2 \cdot 10^5 $ ) — 工厂的电力系数。
- 接下来的 $ N-1 $ 行中的每一行包含两个整数 $ U_j $ 和 $ V_j $ ( $ 1 \le U_j, V_j \le N $ ) — 连接城市 $ U_j $ 和 $ V_j $ 的一条电线。工厂的集合形成了一棵树。

**输出格式**
- 一个整数，代表所有满足 $ 1 \leq x < y < z \leq N $ 的 $ (x, y, z) $ 组合的 $ f(x, y, z) \times g(x, y, z) $ 之和，模 $ 998\,244\,353 $ 后的结果。

**输入输出样例**

**输入样例 #1**
```
3
1 2 3
1 2
2 3
```
**输出样例 #1**
```
0
```

**输入样例 #2**
```
4
6 14 6 6
1 2
2 3
2 4
```
**输出样例 #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 $

所以电力**题意翻译** 在Dengkleknesia国家有 $ N $ 个工厂，编号从 $ 1 $ 到 $ N $。工厂 $ i $ 有一个电力系数 $ A_i $。还有 $ N-1 $ 条电线，第 $ j $ 条电线连接工厂 $ U_j $ 和工厂 $ V_j $。可以保证Dengkleknesia的每个工厂都通过一条或多条电线与Dengkleknesia的其他工厂相连。换句话说，工厂的集合形成了一棵树。Dengkleknesia的每对不同的工厂可以使用一条或多条现有的电线来相互传输电力。但是，每条电线都需要先打开，电力才能通过。 定义 $ f(x, y, z) $ 为需要打开的最少电线数，以便工厂 $ x $ 可以对工厂 $ y $ 和工厂 $ z $ 进行电力传输。同时定义 $ g(x, y, z) $ 为 $ \text{GCD}(A_x, A_y, A_z) $ 的不同质因子数量。 为了衡量电力效率，你必须找到所有满足 $ 1 \leq x < y < 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 $ 的最大整数。 **输入输出格式** **输入格式** - 第一行包含一个整数 $ N $ ( $ 1 \le N \le 2 \cdot 10^5 $ ) — Dengkleknesia的工厂数量。 - 第二行包含 $ N $ 个整数 $ A_1, A_2, \dots, A_N $ ( $ 1 \leq A_i \leq 2 \cdot 10^5 $ ) — 工厂的电力系数。 - 接下来的 $ N-1 $ 行中的每一行包含两个整数 $ U_j $ 和 $ V_j $ ( $ 1 \le U_j, V_j \le N $ ) — 连接城市 $ U_j $ 和 $ V_j $ 的一条电线。工厂的集合形成了一棵树。 **输出格式** - 一个整数，代表所有满足 $ 1 \leq x < y < z \leq N $ 的 $ (x, y, z) $ 组合的 $ f(x, y, z) \times g(x, y, z) $ 之和，模 $ 998\,244\,353 $ 后的结果。 **输入输出样例** **输入样例 #1** ``` 3 1 2 3 1 2 2 3 ``` **输出样例 #1** ``` 0 ``` **输入样例 #2** ``` 4 6 14 6 6 1 2 2 3 2 4 ``` **输出样例 #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 $ 所以电力