6. TokTik Mačiatka

Mňau! Alicka má rada pozeranie smiešnych videí s mačičkami¹ na jej obľúbenej platforme na väzenenie používateľov - TokTiku. Je to jej jediné potešenie v celom živote, pretože predsa čo iné okrem sledovania rozkošných (a občas explodujícich) mňaukadiel by v cez deň robila? Toto však má aj neželané následky. A to také, že keďže Alicka týchto videí pozerá veľa, už skoro všetky pozná! Veľmi ľahko sa tak začne nudiť, hlavne ak jej platforma naservíruje video podobné nejakému, ktoré už v ten deň videla. Algorimus platformy však programujú veľmi milí ľudia, ktorí chcú Alicke iba to najlepšie - a teda, aby bola z videí čo najviac šťastná. Rôzne videá totiž Alicku obšťastnia rôzne, napríklad video kde mačička robí salto ju poteší menej ako video, kde nejaké chutnučké mačiatko mňauká. Títo programátori sú však veľmi neschopní, a tak im musíte pomôcť.

Úloha

Na platforme je \(n\) nových mačičkových videí, ktoré Alicka ešte nevidela. Tieto videá Alicku potešia rôzne - každé video má svoju kvalitu \(a_i\) - teda koľko šťastia toto video dá Alicke po tom, čo si ho pozrie. Niektoré videá sú však podobné niektorým iným videám, pričom pre každé dve videá platí, že existuje práve jedna postupnosť začínajúca jedným a končiaca druhým taká, že každé video je podobné tomu predošlému. Alicka sa začne nudiť (a prestať pozerať videá) práve vtedy, keď začne pozerať nejaké video, ktoré už dnes videla, alebo je podobné nejakému, ktoré dnes už videla. Zistite, koľko najviac šťastia môže Alicka získať pozeraním týchto videí.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) udávajúce počet videí.

Druhý riadok obsahuje \(n\) medzerou oddelených čísel. \(i\)-té z nich udáva hodnotu \(a_i\), teda koľko šťastia dá Alicke \(i\)-té video. Nasleduje \(n-1\) riadkov. Na každom riadku sa nachádzajú dve čísla \(a,b\), pričom toto znamená, že video \(a\) je podobné videu \(b\) (podobnosť je vzájomná, teda aj video \(b\) je podobné videu \(a\)).

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

Za každú sadu viete získať 2 body. V druhej sade navyše platí, že každé video je podobné najviac dvom iným videám. V tretej sade platí, že každé dve videá dajú Alicke rovnako šťastia, teda \(a_0 = a_1 = a_2 \dots = a_{n-1}\).

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - najviac šťastia, ako môže Alicka získať.

Príklad

Input:

5
15 20 13 24 19
0 3
1 2
2 3
3 4

Output:

54

Aj keď by video 3 dalo Alicke najviac šťastia, neoplatí sa jej ho naservírovať. Namiesto toho sa oplatí pozrieť videá 0, 1 a 4.