Cerința

Țăranul Ion are în livada sa N pomi, fiecare cu v[i] mere. Între pomi există N-1 cărări, astfel încât între oricare doi pomi să existe un singur drum, alcătuit eventual din mai multe cărări. Pentru că nu și-a plătit ratele la bancă, el este nevoit să vândă o parte dintre pomi. El vrea să adune merele din livadă, dar pentru că nu are foarte mult timp, el va aduna merele doar dintr-o parte din pomi.

Ion pornește din pomul lui preferat, pomul 1, și se deplasează spre unul din vecinii lui. Pentru că nu este foarte inteligent, atunci când Ion se află la un pom, el se va deplasa către pomul vecin care are cele mai multe mere, fără să ia în calcul ceilalți meri din livadă. Dacă doi pomi au același număr de mere, atunci Ion se va deplasa spre pomul cu numărul de ordine mai mic.

Ajutați-l pe Ion să afle câte mere va aduna folosind metoda sa!

Date de intrare

Pe prima linie a fișierului de intrare mere.in se află un număr natural N, reprezentând numărul de pomi din livadă; pe linia a doua se află N valori v[i], reprezentând numărul de mere din pomul i. Pe următoarele N-1 linii se află câte o pereche de numere x y, cu semnificația că există o cărare de la pomul x la pomul y.

Date de ieșire

Fișierul de ieșire mere.out va conține pe prima linie numărul S, reprezentând numărul total de mere culese.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ v[i] ≤ 10000

Exemplu

mere.in

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

mere.out

5

Explicație

Ion va culege merele din pomii 1 3, obținând 3+2=5 mere.

#include <bits/stdc++.h>



using namespace std;

ifstream cin("mere.in");
ofstream cout("mere.out");

int n , x , y , m[1001] , p , d[1001] , v[1001] , sum , maxi , imax;
vector <int> G[1001];

void bfs(int s)
{
    queue <int> Q;
    v[s] = 1;
    d[s] = 1;
    sum += m[s];
    Q.push(s);
    while(!Q.empty())
    {
        int x = Q.front();
        maxi = 0 , imax = 0;
        for(int i : G[x])
            if(!v[i] && m[i] > maxi)
            {
                maxi = m[i];
                imax = i;
            }
        if(maxi != 0)
        {
            Q.push(imax);
            sum += maxi;
            v[imax] = 1;
        }
        Q.pop();
    }
}


int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
        cin >> m[i];
    for(int i = 1 ; i < n ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(int i = 1 ; i <= n ; i++)
        sort(G[i].begin() , G[i].end());
    bfs(1);
    cout << sum;
}