4-й этап Республиканской олимпиады по информатике 2020-2021, 2 тура

Задача C. Выборы в Массивтобе

Ограничение по времени:

2 секунды

Ограничение по памяти:

1024 мегабайта

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

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

В первой строке находится одно целое число $n$ ($1 <= n <= 77777$). Во второй строке находятся $n$ целых чисел $v_1$, $v_2$, \dots, $v_n$ ($1 <= v_i <= n$). В каждом из следующих $n - 1$ строк находятся два целых числа $a$ и $b$ ($1 <= a, b <= n$, $a \neq b$) означающие существование дороги между домами $a$ и $b$.

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

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

Система оценки

Данная задача содержит $9$ подзадач, в которых выполняются следующие ограничения:

1. Примеры из условия. Оценивается в $0$ баллов.
2. $n <= 100$. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $6$ баллов.
3. $n <= 2000$. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $7$ баллов.
4. $n <= 2000$. Оценивается в $8$ баллов.
5. Гарантируется, что $a_i=1$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $10$ баллов.
6. $v_i <= 100$. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $9$ баллов.
7. Гарантируется, что $a_i=i$, $b_i=i+1$ для всех $i$ ($1 <= i < n$). Оценивается в $13$ баллов.
8. $v_i <= 100$. Оценивается в $12$ баллов.
9. Исходные условия задачи. Оценивается в $35$ баллов.

Пример:

Вход

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

Ответ

13

( Temirlan Satylkhanov )