E. Различающие корни
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Предположим, мы подвесили дерево за вершину $$$v$$$ (сделали эту вершину корнем). Назовем $$$v$$$ различающим корнем, если выполняется следующее условие: в каждом пути из $$$v$$$ до некоторого листа дерева все значения, записанные на вершинах, различны. Значения, встречающихся на различных путях, могут совпадать, но значения на каждом пути, рассматриваемом в отдельности, должны быть различны.

Посчитайте количество различающих корней заданного дерева.

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

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

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Далее следуют $$$n-1$$$ строк, в каждой из которых заданы два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u$$$, $$$v \le n$$$), обозначающих ребро, соединяющее вершины $$$u$$$ и $$$v$$$.

Гарантируется, что данные ребра задают дерево.

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

Выведите одно целое число — количество различающих корней в дереве.

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

В первом примере из условия вершины $$$1$$$, $$$2$$$ и $$$5$$$ — различающие корни.