CF2241E Fair and Square
题目描述
一棵树是一个无向、连通且无环的图。
给定一棵有 $n$ 个顶点的树，每个顶点 $i$ 上写有一个整数 $a_i$。
对于任意两个不同的顶点 $u$ 和 $v$，定义 $p(u, v)$ 为从 $u$ 到 $v$ 的那条唯一简单路径上所有顶点的权值之积。
如果某个无序三元组 $\{u, v, w\}$（$u$、$v$、$w$ 均不同）满足：$p(u,v)\cdot p(v,w)\cdot p(w,u)$ 是一个完全平方数，则称该三元组为“好三元组”。
求给定树中“好三元组”的数量。
注：$^*$ 从顶点 $u$ 到顶点 $v$ 的简单路径是指这样一系列不同的顶点 $u = x_0, x_1, \ldots, x_k = v$，且对所有 $1 \le i \le k$，$x_{i-1}$ 与 $x_i$ 之间有一条边相连。
输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。每个测试用例的描述如下。
每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2\cdot 10^5$），表示树的顶点数。
第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1 \le a_i \le 10^6$），表示每个顶点上的权值。
接下来 $n-1$ 行，每行包含两个整数 $u, v$（$1 \le u,v \le n$），表示树上的一条边。保证所有边组成一棵树。
保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。
输出格式
对于每个测试用例，输出树中“好三元组”的数量。
说明/提示
对于第一个测试用例，所有不同的三个顶点组成的无序三元组都是“好三元组”：
1. $\{1, 2, 3\}$
2. $\{1, 2, 4\}$
3. $\{1, 2, 5\}$
4. $\{1, 3, 4\}$
5. $\{1, 3, 5\}$
6. $\{1, 4, 5\}$
7. $\{2, 3, 4\}$
8. $\{2, 3, 5\}$
9. $\{2, 4, 5\}$
10. $\{3, 4, 5\}$
对于第二个测试用例，只有 $\{2, 5, 8\}$ 是“好三元组”。 
由 ChatGPT 5 翻译