Παράδοση

Δίνεται ένα δέντρο με \( n \) κόμβους, όπου κάθε κόμβος έχει έναν μοναδικό ακέραιο αριθμό από 1 έως \( n \). Το δέντρο είναι ριζωμένο στον κόμβο 1. Κάθε κόμβος έχει έναν ακέραιο αριθμό που ονομάζεται "βάρος". Το βάρος του κόμβου \( i \) είναι \( w_i \).

Ο στόχος σας είναι να βρείτε το μέγιστο δυνατό άθροισμα βαρών μιας απλής διαδρομής στο δέντρο. Μια απλή διαδρομή είναι μια ακολουθία κόμβων όπου κάθε κόμβος εμφανίζεται το πολύ μία φορά.

### Είσοδος

- Η πρώτη γραμμή περιέχει έναν ακέραιο \( n \) \((2 \leq n \leq 100\,000)\) — τον αριθμό των κόμβων στο δέντρο.
- Η δεύτερη γραμμή περιέχει \( n \) ακέραιους αριθμούς \( w_1, w_2, \ldots, w_n \) \((-10^9 \leq w_i \leq 10^9)\) — τα βάρη των κόμβων.
- Κάθε μία από τις επόμενες \( n-1 \) γραμμές περιέχει δύο ακέραιους αριθμούς \( u \) και \( v \) \((1 \leq u, v \leq n)\), που δηλώνουν μια ακμή μεταξύ των κόμβων \( u \) και \( v \).

### Έξοδος

Εκτυπώστε έναν ακέραιο — το μέγιστο δυνατό άθροισμα βαρών μιας απλής διαδρομής στο δέντρο.