|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||512 MB||1||1||1||100.000%|
Binary Casino is a very special skyscraper building consisting of N floors connected by a tricky network of high speed escalators.
The floor connections are designed in a way that if there is an escalator going from floor A to floor B, then there is another escalator going from floor B to floor A as well. Also, for any two floors A and B, there is exactly one way to go from floor A to floor B.
Your manager decided to organize a promotion game to attract more customers. The game has the following rules:
Your manager is curious about the maximum number of tokens a customer can earn in the game.
The first line of input contains an integer N (1 ≤ N ≤ 3 · 105) describing the number of floors in the casino skyscraper. The second line contains N integers Vi (0 ≤ Vi < 220). The i-th integer Vi describes the number of tokens that a customer earns on the i-th floor. After that, N −1 lines follow. Each line contains two integers A and B (0 ≤ A, B < N) which describe an escalator connection between floors A and B.
Output a single number – the maximum number of tokens a customer can earn.
4 1 2 2 1 0 1 1 2 2 3
5 7 3 5 6 7 0 1 1 2 2 3 2 4