Cod sursa(job #1658753)

Utilizator daGramaGrama Matei daGrama Data 21 martie 2016 19:35:10
Problema Asmax Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("asmax.in");
ofstream g("asmax.out");

const int N = 16000;
const int M = 2*N;
int n;
int vf[M],lst[N],urm[M],nr;//lista alok dinamic
int v[N];
int viz[N];
int scor[N];
void adauga(int x, int y){
    //y in lista lui x
    nr++;
    vf[nr]= y;
    urm[nr]=lst[x];
    lst[x]=nr;
}

void dfs(int x){
    viz[x]=1;
    int p,y;
    p=lst[x];
    while(p!=0){
        y=vf[p];
        if(!viz[y]){
            dfs(y);
            if(scor[y] > 0)
                scor[x] += scor[y];
        }
        p=urm[p];

    }
    scor[x] += v[x];
}

int main()
{
    int x,y;
    f>>n;

    for(int i=1;i<=n;i++)
        f>>v[i];
    for(int i=1;i<n;i++){
        f>>x>>y;
        adauga(x,y);
        adauga(y,x);
    }
    dfs(1);


    int maxim=scor[1];
    for(int i=1;i<=n;i++){
        if(scor[i]>maxim)
            maxim=scor[i];
    }
    g<<maxim;
    return 0;
}