E. Это квадрат, честно
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Деревом называется связный граф без циклов.

Дано дерево из $$$n$$$ вершин. На каждой вершине $$$i$$$ записано число $$$a_i$$$.

Для любой пары вершин $$$u$$$ и $$$v$$$ ($$$u \ne v$$$), определим $$$p(u, v)$$$ как произведение чисел, записанных на единственном простом пути$$$^{\text{∗}}$$$ из $$$u$$$ в $$$v$$$.

Неупорядоченная тройка вершин $$$\{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\}$$$ является одной из хороших троек.