turism

Andreea şi Ioana au ajuns în judeţul Tinichea şi doresc să viziteze cât mai multe obiective turistice. Judeţul Tinichea este format din $N$ oraşe, între unele dintre aceste oraşe existând şosele bidirecţionale. Mai exact, orice şosea leagă direct două oraşe, iar şoselele sunt dispuse astfel încât între oricare două oraşe din judeţ să existe un drum unic. Un drum este o succesiune de oraşe astfel încât între oricare două oraşe consecutive pe drum există o şosea ce le leagă. Oraşele sunt numerotate de la $1$ la $N$ şi pentru fiecare oraş se cunoaşte $C_i$, numărul de obiective turistice din oraşul $i$.

Fiindcă s-au certat puţin în ultima vreme, cele două fete vor să aleagă fiecare câte un drum astfel încât numărul de obiective pe care le vizitează Andreea adunat cu numărul de obiective pe care le vizitează Ioana să fie maxim. Condiţiile pe care le pun fetele sunt ca drumurile lor să nu aibă niciun oraş în comun, iar orice oraş să fie vizitat cel mult o singură dată.

Cerinţă

Determinaţi pentru cele două fete care este numărul total maxim de obiective pe care le pot vizita, respectând condiţiile din enunţ.

Date de intrare

Fişierul de intrare turism.in va conţine $12$ seturi de date de intrare. Prima linie a unui set de date de intrare va conţine numărul natural $N$, reprezentând numărul de oraşe. Pe următoarea linie a setului de date se vor afla $N$ numere naturale $C_1 \ C_2 \ C_3 \dots C_{N-1} \ C_N$, reprezentând, în ordine, numărul de obiective turistice din fiecare oraş. Urmează $N-1$ linii pe care se află câte două numere naturale distincte $A \ B$ cu semnificaţia că există o şosea între oraşele $A$ şi $B$. Valorile de pe aceeaşi linie sunt separate prin spaţiu.

Date de ieșire

Fişierul de ieşire turism.out va conţine $12$ linii, pe linia $i$ aflându-se răspunsul pentru al $i$-lea set de date de intrare.

Restricții și precizări

• $2 \leq N \leq 100 \ 000$
• $1 \leq C_i \leq 9 \ 999 (1 \leq i \leq N)$
• Pentru $20\%$ din teste $2 \leq N \leq 100$
• Pentru $20\%$ din teste $101 \leq N \leq 800$
• Toate numerele din fişierul de intrare sunt numere naturale.

Exemplu

turism.in

2
1 1 
1 2
...
3
1 2 3
1 2
1 3

turism.out

2
...
6

Explicație

Fişierul de intrare trebuie să conţină $12$ teste, în exemplu sunt prezentate doar primul şi ultimul dintre cele $12$.
Pentru primul test există $2$ oraşe, în fiecare oraş fiind câte un obiectiv turistic. Există o singură şosea (de la $1$ la $2$). Soluţia optimă este $2$ (fiecare fată vizitează câte un oraş).
Pentru ultimul test există $3$ oraşe, având $1$, $2$ respectiv $3$ obiective turistice) şi $2$ şosele (între $1$ şi $2$, respectiv între $1$ şi $3$). Soluţia optimă este $6$.
Punctele de suspensie ... indică faptul că lipsesc cele $10$ teste.