/*
Soluzione super mario di Barberis Enrico
Algoritmo:
l'esrcizio camuffa il fatto che il grafo in realtà è un albero
infatti un grafo con N nodi e con N-1 archi non potrà mai essere un grafo
La soluzone diventa molto più semplice:
basta fare una semplice visità per profondità(ho usato la ricorsione per un codice più corto)
e appena si arriva a una foglia segnarsi la quantità di funghi raggiunta e se è maggiore
della quantità massima totale aggiorno il massimo.
Complessità: O(N) //Spero di averla calcolata giusta
*/
#include<iostream>
#include<fstream>
using namespace std;
//Struttura del bosco: sin e des indica rispettivamente il figlio sinistro
//e il figlio destro di quel nodo dell'albero
struct zona{
int sin;
int des;
int funghi; //indica il numero di funghi di quella zona
};
zona bosco[100000]; //Tabella di tutte le zone del bosco
int n; //Numero zone
int massimo=0; //Numero massimo di funghi
void leggi(){
int x,y;//Variabili per la lettura
ifstream fin("input.txt");
fin>>n;//legggo n
for(int i=1; i<=n; i++) fin>>bosco[i].funghi;//leggo quantità dei funghi per ogni nodo dell'albero
for(int i=1; i<=(n-1); i++){//leggo tutti gli archi dell'albero
fin>>x>>y;//legggo i due nodi
//li collego(notare 0 indica che non sono collegati)
//l'id serve per controllare che l'arco sinistra non venga riscritto da quello di destra
if(bosco[x].sin==0) bosco[x].sin=y;
else bosco[x].des=y;
}
}
//Funziona ricorsiva
//Parametro nodo: indica il nodo in cui la visita è arrivata in quel momento
//Parametro funghi: indica il numero di funghi massimo che si può ottenere fino a quel nodo
void visita(int nodo, int funghi){
if(bosco[nodo].sin==0 && bosco[nodo].des==0){//Se sono arrivato a una foglia dell'albero
if(funghi > massimo) massimo=funghi;//aggiorno la quantità massima di funghi
}
else{//altrimenti se non sono in una foglia dell'albero
//visito tutti i due figli(se esisitono) cona la quantità di funghi ottenuta fino a quel momento
//sommata alla quantità di funghi nel nodo in cui si sta per visitare
if(bosco[nodo].sin!=0) visita(bosco[nodo].sin,funghi+bosco[bosco[nodo].sin].funghi);
if(bosco[nodo].des!=0) visita(bosco[nodo].des,funghi+bosco[bosco[nodo].des].funghi);
}
}
int main(){
//Leggo dati
leggi();
//Inizio visita da 1 con quantià di funghi presenti nella zona 1(quella di partenza)
visita(1,bosco[1].funghi);
//Arrivato a questo punto la variabile out vale quanto il numero massimo di funghi ottenibile
//stampo massimo
ofstream fout("output.txt");
fout<<massimo;
fout.close();
//Fine
return 0;
}