Cod sursa(job #1111921)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 19 februarie 2014 11:35:56
Problema Asmax Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include<cstdio>
#include<vector>
#define NMAX 16010

using namespace std;

vector<int> a[NMAX];
int n, sol, vz[NMAX], D[NMAX], V[NMAX];

void Citeste()
{
  int i, x, y;
  freopen("asmax.in", "r", stdin);
  scanf("%d", &n);
  for (i=1; i<=n; ++i)
  {
    scanf("%d", &V[i]);
    D[i]=V[i];
  }
  sol=D[1];
  for (i=1; i<n; ++i)
  {
    scanf("%d%d", &x, &y);
    a[x].push_back(y);
    a[y].push_back(x);
    sol=max(sol, D[i+1]);
  }
}

void DFS(int nod)
{
  int i;
  vz[nod]=1;
  for (i=0; i<a[nod].size(); ++i)
    if (!vz[a[nod][i]])
    {
      DFS(a[nod][i]);
      if (D[a[nod][i]]>0) D[nod]+=D[a[nod][i]];
    }
  sol=max(sol, D[nod]);
}

int main()
{
  Citeste();
  DFS(1);
  freopen("asmax.out", "w", stdout);
  printf("%d\n", sol);
  return 0;
}