当前没有测试数据。

题目描述

树是一张无环的无向连通图。

给定一棵具有 $n$ 个顶点的树，每个顶点 $i$ 上写有整数 $a_i$。

对于任意两个顶点 $u,v$（$u\neq v$），定义 $p(u,v)$ 为 $u$ 到 $v$ 的唯一简单路径上所有顶点权值的乘积。

一个由三个互不相同顶点构成的无序三元组 $\{u,v,w\}$，当且仅当 $p(u,v)\cdot p(v,w)\cdot p(w,u)$ 是完全平方数时，称该三元组为好三元组。

请求出树中好三元组的总数量。

简单路径定义：从顶点 $u$ 到 $v$ 的简单路径是一列互不相同顶点 $u=x_0,x_1,\dots,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$。

输出格式

对每组测试用例，输出树中好三元组的数目。

4
5
1 1 1 1 1
1 2
2 3
2 4
4 5
10
1 2 3 4 5 6 7 8 9 10
1 3
2 6
6 7
5 4
8 3
3 4
4 6
9 1
10 2
6
12 6 3 18 9 2
3 4
4 5
2 6
6 1
4 2
8
3 16 9 1 8 16 4 9
2 1
3 1
4 3
3 5
6 3
4 7
8 1

10
48
0
40

说明

第一组测试样例中，所有由3个不同顶点组成的无序三元组都是好三元组，一共10个。

第二组测试样例中，$\{2,5,8\}$ 就是一个好三元组。

原题链接

原题链接