CF2241E.Fair and Square

普及/提高-

通过率：0%

时间限制：3.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

A tree is an undirected connected graph with no cycles.

You are given a tree having $n$ vertices. Each vertex $i$ has an integer value $a_i$ written on it.

For any two vertices $u$ and $v$ ( $u \ne v$ ), define $p(u, v)$ as the product of the values written on the vertices lying on the unique simple path $^{\text{∗}}$ from $u$ to $v$ .

An unordered triplet of three distinct vertices ${u, v, w}$ is called good if and only if: $p(u,v)\cdot p(v,w)\cdot p(w,u)$ is a perfect square.

Determine the number of good unordered triplets in the given tree.

$^{\text{∗}}$ A simple path from the vertex $u$ to vertex $v$ is a sequence of distinct vertices $u = x_0, x_1, \ldots, x_k = v$ such that there exists an edge between vertices $x_{i-1}$ and $x_i$ for all $1 \le i \le k$ .

树是一类无向连通图，且不含环。

给定一棵包含 $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$ ，其中所有顶点互不相同，且对每个 $1 \le i \le k$ ，顶点 $x_{i-1}$ 与 $x_i$ 之间均存在一条边。

输入格式

The first line contains an integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases. The description of each test case follows.

Each test case begins with an integer $n$ ( $3 \le n \le 2\cdot 10^5$ ) — the number of vertices.

The second line contains $n$ integers $a_1,a_2,\dots,a_n$ ( $1 \le a_i \le 10^6$ ) — the integer values written on the vertices.

Each of the next $n-1$ lines contains two integers $u,v$ ( $1 \le u,v \le n$ ), denoting an edge of the tree. It is guaranteed that the edges form a tree.

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot 10^5$ .

第一行包含一个整数 $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$ 。

输出格式

For each test case output the number of good triplets in the tree.

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

输入输出样例

输入#1

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

输出#1

说明/提示

For the first test case, all the unordered triplets of three distinct vertices are good:

${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}$

For the second test case, ${2, 5, 8}$ is a good triplet.

对于第一个测试用例，所有由三个互不相同的顶点构成的无序三元组都是“好”的：

${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}$

对于第二个测试用例， ${2, 5, 8}$ 是一个“好”的三元组。

输入解题思路，AI测评打分。不知道怎么写?

首页