Республиканская олимпиада по информатике 2021 года за 11 класс | Казахстанские олимпиады

Выборы в Массивтобе

В городе Массивтобе проводятся очередные выборы акима. Массивтобе – современный город имеющий систему дорог в виде дерева. В нем есть $n$ домов соединенных $n − 1$ двусторонними дорогами так, что из каждого дома можно добраться до всех остальных передвигаясь по этим дорогам.

Айбар — начинающий блогер, который хочет осветить выборы. Он решил снять видео социального опроса в котором он собирается идти по простому пути в городе и спрашивать за кого голосует жители каждого дома. Путь считается простым если он проходит по каждой вершине не более одного раза.

Айбар знает, что видео не наберет много просмотров если в нем не будет доминантного кандидата. Кандидат считается доминантным если более половины опрошенных в видео голосуют за него.

Всего есть $n$ кандидатов с номерами от $1$ до $n$. Вам дан список $v_1, v_2, . . . , v_n$, где значение $v_i$ означает, за кого голосуют жители $i$-го дома. Чтобы произвести как можно больше контента Айбар просит вас посчитать сколько есть различных путей в Массивтобе с доминантным кандидатом. Путь идущий из вершины $v$ в вершину $u$, считается таким же как и путь из $u$ в $v$.

Формат входного файла

В первой строке находится одно целое число $n (1 \leq n \leq 77777)$.

Во второй строке находятся $n$ целых чисел $v_1, v_2, . . . , v_n (1 \leq v_i \leq n)$.

В каждом из следующих $n − 1$ строк находятся два целых числа $a$ и $b (1 \leq a, b \leq n, a \neq b)$ означающие существование дороги между домами $a$ и $b$.

Формат выходного файла

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

Примеры

Вход

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

Выход

13