Deblo

Πριν από περίπου τριάντα χρόνια, ο νεαρός Krešo συμμετείχε για πρώτη φορά στον εθνικό διαγωνισμό πληροφορικής. Όπως και σήμερα, η έναρξη του διαγωνισμού αποτελούνταν από μια σειρά ομιλητών που προσπάθησαν να δείξουν τη σημασία αυτής της διοργάνωσης στους διαγωνιζόμενους, μέσω εμψυχωτικών μηνυμάτων. Το κοινό, με ενθουσιασμό, άρχισε να χειροκροτεί κάθε δύο δευτερόλεπτα, αλλά ο Krešo εκνευρίστηκε με μια φράση. Συγκεκριμένα, ένας από τους ομιλητές ισχυρίστηκε ότι εκτιμούσε περισσότερο τη λογική πράξη AND παρά τη λογική πράξη OR επειδή, ανεξάρτητα από την ταυτότητα του νικητή, γι' αυτόν και ο Mirko και ο Slavko ήταν νικητές του εθνικού διαγωνισμού, αντί ο νικητής να είναι μόνο ο Mirko ή μόνο ο Slavko. Ο Krešo τρελάθηκε, σηκώθηκε και άρχισε να εξηγεί στο κοινό ότι πρόκειται για μια πράξη γνωστή ως​exclusive OR (γνωστή ως XOR). Αφού έδωσε τη διάλεξή του, έδωσε στον διακεκριμένο ομιλητή την επόμενη εργασία για να επαληθεύσει την κατανόησή του.

Υπάρχει ένα δεδομένο δέντρο που αποτελείται από ~N~ κόμβους, όπου σε κάθε κόμβο εκχωρείται μια τιμή. Η τιμή μιας διαδρομής σε αυτό το δέντρο ορίζεται ως το exclusive OR των τιμών όλων των κόμβων σε αυτό το μονοπάτι. Το καθήκον σας είναι να προσδιορίσετε το άθροισμα των τιμών όλων των μονοπατιών του δέντρου, συμπεριλαμβανομένων των μονοπατιών που περιέχουν μόνο έναν κόμβο.

Τριάντα χρόνια αργότερα, ο Krešo έπεισε επιτέλους τους συντάκτες των προβλημάτων COCI να συμπεριλάβουν αυτή την εργασία σε έναν από τους γύρους. Βοηθήστε μας να δώσουμε ξανά την πίστη για τον διαγωνιστικό προγραμματισμό στον Krešo.

Σημείωση: Το exclusive OR (⊕) είναι μια δυαδική πράξη που εφαρμόζεται χωριστά σε κάθε ζεύγος των αντίστοιχων δυαδικών ψηφίων των δύο τελεστών του, έτσι ώστε κάποιο bit στο αποτέλεσμα να ορίζεται ως 1, εάν και μόνο εάν αυτό το bit έχει οριστεί να είναι 1, σε έναν ακριβώς τελεστή.

Είσοδος

Η πρώτη γραμμή περιέχει έναν θετικό ακέραιο αριθμό ~N (1 \le N \le 100\,000)~ που υποδηλώνει τον αριθμό των κόμβων στο δέντρο.
Η δεύτερη γραμμή περιέχει ~N~ ακέραιους αριθμούς ~v_i (0 \le v_i \le 3\,000\,000)~, που χωρίζονται με κενό και η i-οστή τιμή αντιπροσωπεύει την τιμή του i-οστού​κόμβου.
Οι ακόλουθες γραμμές ~(N-1)~ περιέχουν δύο αριθμούς ~a_j~ και ~b_j (1 \le a_j, b_j \le N)~, που υποδεικνύουν ότι υπάρχει μια άκρη μεταξύ των κόμβων ~a_j~ και ~b_j~.

Έξοδος

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

Βαθμολογία

Σε δοκιμαστικές περιπτώσεις αξίας 30% των συνολικών πόντων, το ~N~ θα είναι μικρότερο ή ίσο με 200.
Σε δοκιμαστικές περιπτώσεις αξίας 50% των συνολικών πόντων, το ~N~ θα είναι μικρότερο ή ίσο με 1.000.
Σε δοκιμαστικές περιπτώσεις αξίας επιπλέον 20% των συνολικών πόντων, κάθε κόμβος ~x = 1, 2, ..., N-1~ θα συνδεθεί με τον κόμβο ~x+1~.

Παραδείγματα

input

3
1 2 3
1 2
2 3

output

10

Επεξήγηση του 1ου παραδείγματος:

• Η τιμή της διαδρομής από τον κόμβο 1 στον κόμβο 1 είναι 1
• Η τιμή της διαδρομής από τον κόμβο 1 στον κόμβο 2 είναι 1 ⊕ 2 = 3
• Η τιμή της διαδρομής από τον κόμβο 1 στον κόμβο 3 είναι 1 ⊕ 2 ⊕ 3 = 0
• Η τιμή της διαδρομής από τον κόμβο 2 στον κόμβο 2 είναι 2
• Η τιμή της διαδρομής από τον κόμβο 2 στον κόμβο 3 είναι 2 ⊕ 3 = 1
• Η τιμή της διαδρομής από τον κόμβο 3 στον κόμβο 3 είναι 3

Το άθροισμα όλων των μονοπατιών είναι 1 + 3 + 0 + 2 + 1 + 3 = 10.

input

5
2 3 4 2 1
1 2
1 3
3 4
3 5

output

64

input

6
5 4 1 3 3 3
3 1
3 5
4 3
4 2
2 6

output

85