← 返回题目列表

Codeforces · 2241/E

E. 公平公正

中文机器翻译题面 查看原题

树是没有环的无向连通图。

给你一棵有 $$$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$$$。

输出

对于每个测试用例,输出树中良好三元组的数量。

示例

输入
复制

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

注意

对于第一个测试用例,三个不同顶点的所有无序三元组都是好的:

  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\}$$$ 是一个很好的三元组。