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

Есеп С. Массивтөбедегі сайлау

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

2 seconds

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

1024 megabytes

Массивтөбе қаласында әкім сайлауы болайын деп жатыр. Массивтөбеде $n$ үй және оларды байланыстыратын $n - 1$ жол бар. Осы жолдар арқылы әр үйден кез келген үйге жетуге болады. Айбар жаңа бастап жүрген блогер. Ол бір жай жолмен жүріп үйдің адамы кімге дауыс беретінің сұрауды видеоға түсіруді шешті. Жай жол деп, әр үйден жәңе әр жолдан ең көп дегенде бір рет өтетін жолды айтамыз. Айбар біледі, видеода көп қарау болмайды, егер ода доминант үміткер болмаса. Үміткер доминант деп аталады, егер ол сұралған адамдардың ішінде жартысынан көп дауыс алатын болса. Сізге $v_1, v_2, ..., v_n$ әр үйдің адамы кімге дауыс берілетіні айтылады. Қызық контент жасау үшін Айбар, доминанты бар қанша әр түрлі жол бар екенің санағысы келеді. $v$ үйінен $u$ға, $u$ үйінен $v$-ға жолдары бірдей болып саналады.

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

Бірінші жолда $n(1 <= n <= 77777)$. Екінші жолда $n$ бүтін сан $v_1,v_2,..,v_n(1 <= v_i <= n)$. Келесі $n - 1$ жолда екі бүтін сан $a$ және $b(1 <= a,b <= n)$ — $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 )