Вам дано дерево, состоящее из \(n\) вершин, пронумерованных от \(1\) до \(n\). Каждая вершина окрашена в некоторый цвет, обозначенный целым числом от \(1\) до \(n\).
Простой путь в дереве называется красивым, если:
Посчитайте количество красивых простых путей в дереве. Обратите внимание, что пути считаются ненаправленными (то есть путь из \(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
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач