树是没有环的无向连通图。
给你一棵有 $$$n$$$ 个顶点的树。每个顶点 $$$i$$$ 上都写有一个整数值 $$$a_i$$$。
对于任意两个顶点 $$$u$$$ 和 $$$v$$$ ($$$u \ne v$$$),将 $$$p(u, v)$$$ 定义为写在从 $$$u$$$ 到 $$$v$$$ 的唯一简单路径 $$$^{\text{∗}}$$$ 上的顶点上的值的乘积。
三个不同顶点 $$$\{u, v, w\}$$$ 的无序三元组称为 好 当且仅当: $$$p(u,v)\cdot p(v,w)\cdot p(w,u)$$$ 是 完美正方形.
确定数量 好 给定树中的无序三元组。
$$$^{\text{*}}$$$从顶点 $$$u$$$ 到顶点 $$$v$$$ 的简单路径是一系列不同的顶点 $$$u = x_0, x_1, \ldots, x_k = v$$$ 使得顶点 $$$x_{i-1}$$$ 和$$$x_i$$$ 对于所有 $$$1 \le i \le k$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出树中良好三元组的数量。
示例
输入复制
451 1 1 1 11 22 32 44 5101 2 3 4 5 6 7 8 9 101 32 66 75 48 33 44 69 110 2612 6 3 18 9 23 44 52 66 14 283 16 9 1 8 16 4 92 13 14 33 56 34 78 1
输出复制
1048040
注意
对于第一个测试用例,三个不同顶点的所有无序三元组都是好的:
- $$$\{1, 2, 3\}$$$
- $$$\{1, 2, 4\}$$$
- $$$\{1, 2, 5\}$$$
- $$$\{1, 3, 4\}$$$
- $$$\{1, 3, 5\}$$$
- $$$\{1, 4, 5\}$$$
- $$$\{2, 3, 4\}$$$
- $$$\{2, 3, 5\}$$$
- $$$\{2, 4, 5\}$$$
- $$$\{3, 4, 5\}$$$