Cod sursa(job #1117498)

Utilizator mvcl3Marian Iacob mvcl3 Data 23 februarie 2014 16:37:57
Problema Asmax Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>
#include <vector>

#define in "asmax.in"
#define out "asmax.out"
#define oo 16000000
#define Max_Size 16009

std :: ifstream f(in);
std :: ofstream g(out);

int N, sol = -oo, A[Max_Size], DP[Max_Size];
std :: vector < int > V[Max_Size];

inline void Read_Data() {
    f >> N;
    for(int i = 1; i <= N; ++i) f >> A[i], DP[i] = -oo;

    for(int x, y, i = 1; i < N; ++i) {
        f >> x >> y;

        V[x].push_back(y);
        V[y].push_back(x);
    }
}

void DF(int nod) {
    DP[nod] = A[nod];

    for(auto val : V[nod])
        if(DP[val] == -oo) {
            DF(val);
            DP[nod] = std :: max(DP[nod], DP[nod] + DP[val]);
        }

    sol = std :: max(sol, DP[nod]);
}

int main() {
    Read_Data();
    DF(1);

    g << sol << '\n';

    g.close();
    return 0;
}