MEXimum

aritra741 Amra shobai Raja
Limits 1s, 512 MB

Let’s get straight to the point. You are given a tree. In the tree, each node uu has a number aua_u assigned to it. The score of a node uu is defined as the MEXMEX of all the numbers on the simple path from 11 to uu.



Suppose, a=[0,2,1,4,21,2]a=[0,2,1,4,21,2]. The list of values on the path from 11 to the node 66 is [0,1,2][0,1,2]. The minimum non-negative excluded number or MEXMEX of this list is 33. So the score of node 66 is 33.

You have to print the maximum score among all the nodes.


  • A tree is a connected graph with nn nodes and n1n-1 edges.

  • The MEX of a list of numbers is the minimum non-negative number that is not included in the list. For example, MEX([0,1,4,5])=2MEX( [0,1,4,5] )= 2.

Input

The first line contains an integer n(1n105)n ( 1 \leq n \leq 10^5 ) — the number of nodes.

The second line contains nn integers a1,a2,,ana_1, a_2, …, a_n(0ai1018)( 0 \leq a_i \leq 10^{18} ).

Each of the next n1n-1 lines contains 2 values uu and vv, indicating that there is an edge between uu and vv in the tree.

Output

Print one integer — the maximum score among all the nodes.

Sample

InputOutput
6
0 2 1 4 21 2
1 2
2 4
1 3
3 5
3 6
3

score of node 11 is MEX([0])=1MEX([0])=1

score of node 22 is MEX([0,2])=1MEX([0, 2])=1

score of node 33 is MEX([0,1])=2MEX([0, 1])=2

score of node 44 is MEX([0,2,4])=1MEX([0, 2, 4])=1

score of node 55 is MEX([0,1,21])=2MEX([0, 1, 21])=2

score of node 66 is MEX([0,1,2])=3MEX([0, 1, 2])=3

Hence, the maximum score among all the nodes is 3\boxed{3}.


Submit

Login to submit.

Statistics

71% Solution Ratio
AlfehsaniEarliest, 1M ago
BinaryBeast007Fastest, 0.0s
fatmathmanLightest, 19 kB
MrBrionixShortest, 759B
Toph uses cookies. By continuing you agree to our Cookie Policy.