img
Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
acm
ˇ a
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
s
cz
ˇ
University of Zilina
Masaryk University
Matej Bel University in Bansk´ Bystrica
a
University of West Bohemia
CTU Open Contest 2018
Escalators
escalators.c, escalators.cpp, escalators.c11, Escalators.java, escalators.py
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:
· The game is played in one or more rounds.
· In each round a customer can choose a floor S on which that round starts. At this moment
he earns some fixed number of tokens t(S) associated with floor S. Then he may move to
other floors using escalators.
· If a customer decides to take an escalator from floor A to floor B and has X tokens he
has to pay X - (X AND t(B)) tokens to enter floor B, where "AND" is a bitwise AND
operator, "-" is a standard minus operator on numbers, and t(B) is a number of tokens
associated with floor B.
· A customer can decide to stop the round on any floor (including S) and keep the tokens
from that round. Then he can start a new round from any floor if it is possible.
· No two rounds may have the same pair of starting and ending floors, not even in the
opposite direction, i.e. when considering exchanged starting and ending floors.
Your manager is curious about the maximum number of tokens a customer can earn in the game.
Input Specification
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 Specification
Output a single number ­ the maximum number of tokens a customer can earn.
Output for Sample Input 1
Sample Input 1
8
4
1
221
0
1
1
2
2
3
Sample Input 2
Output for Sample Input 2
5
48
7
3567
0
1
1
2
2
3
2
4