Problem H
Dalarna

Dalarnas vägnät består av $N$ städer och $N-1$ vägar. Varje väg förbinder två städer direkt. Om en taxi befinner sig i en stad, kan den åka till alla städer som är direkt anslutna till den via en väg. Dessutom är nätverket konstruerat så att det alltid går att färdas mellan varje par av städer genom en eller flera vägar.

För varje stad $i$ behöver Harry se till att minst $p_i$ taxibilar passerar genom staden för att nå sitt mål. En taxibil åker mellan två bestämda städer i nätverket och färdas längs den kortaste vägen.

För att inte väcka misstankar vill Harry använda så få taxibilar som möjligt. Hjälp honom att räkna ut det minsta antal taxibilar han behöver beställa för att uppfylla kraven.

Indata

Den första raden innehåller ett heltal $N$ ($1 \le N \le 10^5$), antalet städer i Dalarna.

Den andra raden innehåller $N$ heltal $p_1, p_2, ..., p_N$ ($0 \le p_i \le 10^9$), där $p_i$ anger hur många taxibilar som måste passera genom stad $i$.

De följande $N-1$ raderna beskriver vägarna mellan städerna. Varje rad innehåller två heltal $u$ och $v$ ($1 \le u, v \le N$), vilket betyder att det finns en väg mellan stad $u$ och stad $v$. Vägnätet sammankopplar alla städer.

Utdata

Skriv ut ett heltal: det minsta antalet taxibilar som Harry behöver beställa.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Figure 1: Vägnätverket för de 6 städerna i exempelfall 3.

Figure 2: En möjlig lösning för exempelfall 3, där de blåa, oranga, lila, gröna och röda vägarna är 5 olika taxibilars färd.

3
3 1 5
1 2
2 3

5

4
1 2 2 2
1 3
4 2
3 2

2

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

5