CF1725E Electrical Efficiency

在 Dengkleknesia 国，有 $N$ 个工厂，编号从 $1$ 到 $N$。第 $i$ 个工厂的电系数为 $A_i$。此外，还有 $N-1$ 条电力线，第 $j$ 条电力线连接工厂 $U_j$ 和工厂 $V_j$。可以保证 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$ 行中，第 $j$ 行包含两个整数 $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$ 取模后的结果。

在第一个样例中，唯一满足条件的 $(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$。 由 ChatGPT 4.1 翻译