404186: GYM101445 J Чокнутый профессор-2

J. Чокнутый профессор-2ограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Быстро летит время год за годом. И снова, как и каждый год, профессор МИСиСа задал группе студентов подготовить курсовую работу на тему: "Расчет воздухонагревателя доменной печи". В назначенный день и час все студенты принесли курсовые работы и дружно скопировали их на компьютер профессора.

Профессору стало интересно: а какова вероятность того, что студенты списали работы друг у друга? Для того чтобы это проверить, он решил просто сравнить названия папок и файлов в своей файловой системе. Файловая система профессора представляет из себя корневое дерево (то есть дерево с выделенным корнем), на каждой вершине которого написано некоторое целое число (название). Более того, как и в обычной файловой системе, внутри папки не может содержаться двух файлов (папок) с одинаковыми названиями.

Профессор считает, что каждая пара изоморфных корневых поддеревьев в его файловой системе является кандидатом на списанные курсовые. Для начала ему интересно посчитать, сколько таких пар существует. Помогите ему в этом.

Напомним, что корневое поддерево состоит из заданной вершины-корня и всех ее потомков.

Два корневых поддерева являются изоморфными, если каждой вершине первого поддерева можно однозначно поставить в соответствие ровно одну вершину второго поддерева таким образом, чтобы:

(a) каждая вершина второго поддерева соответствовала ровно одной вершине первого поддерева, причем с тем же самым значением;

(б) корень первого поддерева соответствовал корню второго поддерева;

(в) две вершины первого поддерева были соединены ребром тогда и только тогда, когда ребром соединены соответствующие вершины второго поддерева.

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

В первой строке дано целое число n – количество вершин в дереве, 2 ≤ n ≤ 10⁵.

В следующих (n - 1) строках через пробел даны по два целых числа u_i и v_i – номера вершин, которые соединяет i-тое ребро дерева, 1 ≤ u_i,  v_i ≤ n, u_i ≠ v_i, 1 ≤ i ≤ n.

В последней строке через пробел даны n целых чисел c_i – значения вершин дерева, 1 ≤ c_i ≤ 10⁹, 1 ≤ i ≤ n.

Корень дерева находится в вершине номер 1.

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

Выведите единственное число – количество пар изоморфных корневых поддеревьев.

ПримерыВходные данные

4
1 2
1 3
3 4
1 2 3 2

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

1

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

6
1 2
1 3
1 4
3 5
4 6
1 2 3 4 2 2

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

3