E. Посчитай пути
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево, состоящее из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$. Каждая вершина окрашена в некоторый цвет, обозначенный целым числом от $$$1$$$ до $$$n$$$.

Простой путь в дереве называется красивым, если:

  • он состоит хотя бы из $$$2$$$ вершин;
  • первая и последняя вершины пути имеют одинаковый цвет;
  • ни одна другая вершина на пути не имеет такой же цвет, как и первая вершина.

Посчитайте количество красивых простых путей в дереве. Обратите внимание, что пути считаются ненаправленными (то есть путь из $$$x$$$ в $$$y$$$ — это то же самое, что и путь из $$$y$$$ в $$$x$$$).

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого теста записано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Во второй строке записаны $$$n$$$ целых чисел $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — цвет каждой вершины.

В $$$i$$$-й из следующих $$$n - 1$$$ строк записаны два целых числа $$$v_i$$$ и $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \neq u_i$$$) — $$$i$$$-е ребро дерева.

Данные ребра образуют валидное дерево. Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество красивых простых путей в дереве.

Пример
Входные данные
4
3
1 2 1
1 2
2 3
5
2 1 2 1 2
1 2
1 3
3 4
4 5
5
1 2 3 4 5
1 2
1 3
3 4
4 5
4
2 2 2 2
3 1
3 2
3 4
Выходные данные
1
3
0
3