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

Explicație

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Mere:

//Complexitate O(N^2) timp si memorie
//Metoda: Greedy pe arbore

#include <fstream>
using namespace std;

const int N = 1005;

ifstream fin ("mere.in");
ofstream fout ("mere.out");

int n, v[N], sum;
bool a[N][N];

void dfs(int x, int father) {
    sum += v[x];
    int poz = 0;
    for (int i = 1; i <= n; ++i)
        if (i != father && a[x][i] && v[poz] < v[i])
            poz = i;
    if (poz)
        dfs(poz, x);
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    for (int i = 0, x, y; i < n; ++i) {
        fin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    dfs(1, -1);
    fout << sum;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #550 Mere

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #550 Mere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #550 Mere