시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 9 | 6 | 5 | 62.500% |
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
8
5 7 3 5 6 7 0 1 1 2 2 3 2 4
48