6. Taylor sendvič

Taylor Swift má hlad. Tiež má tanier. Ale nemá sendvič. Našťastie má súkromný raketoplán, ktorým aj tak plánuje prejsť cestu po galaxií. Galaxia má tvar stromu. Cesta vyzerá ako postupnosť planét (vrcholov), ktoré sú spojené hranami a neopakujú sa. Počas tejto cesty si teda spraví sendvič, ale nie obyčajný ale taký galaktický. Galaktický sendvič zostaví tak, že počas svojej cesty vystrčí tanier z raketoplánu. Zakaždým, keď prejde okolo nejakej planéty, prilepí sa jej jedna miestna surovina na vrch. Suroviny môžu byť rôzne, no aby to predsa len bol sendvič, musí mať na vrchu a na spodku rovnakú surovinu. Tiež ak je surovina na spodku, nemôže byť nikde inde v sendviči, až po vrch sendviča[^1].

Zatiaľ si však nie je istá, kade pôjde, ukáže vám teda mapu galaxie a pre každú planétu, ktorú surovinu tam dostane na sendvič. Zaujíma ju koľko existuje rôznych ciest takých, aby jej vznikol správne vyzerajúci galaktický sendvič. Smer cesty nás nezaujíma, teda cesta z vrcholu A do B sa ráta za tú istú ako z B do A.

Úloha

Presnejšie ju teda zaujíma, koľko je v galaxií (ktorá je v tvare stromu) ciest takých, že sa začínajú a končia planétou s tým istým typom jedla, pričom na ceste medzi nimi taký typ nie je.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) udávajúce počet planét v galaxií (počet vrcholov v strome).

Na ďalšom riadku je \(n\) čísel \(c_i\), identifikátory jedla ktoré Taylor Swift dostane na \(i\)-tej planéte.

Nasleduje \(n-1\) riadkov, na každom dvojica rôznych čísel \(a_i, b_i\), (\(1 \leq a_i, b_i \leq n\)), dva vrcholy, ktoré spája hrana.

V jednotlivých sadách platia nasledujúce obmedzenia:

Navyše v tretej sade je garantované, že strom je cesta, na ktorej sú vrcholy v poradí od \(1\) po \(n\). Teda \(i\)-ta hrana ide z vrcholu $i do \(i+1\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo, počet rôznych ciest, ktoré vytvoria správny sendvič.

Príklad

Input:

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

Output:

5

Správne cesty existujú medzi dvojicami vrcholov (1, 5), (3, 4), (3, 6), (3, 7), (6, 7).

[^1] Veď ani v pozemskom sendviči nemôže byť chlieb niekde v strede.