MEX on Trees Codechef Solution | MARCH CHALLENGE

MEX on Trees Codechef Solution

Consider a tree with NN nodes, rooted at node 11.
The value of the ithith node (1≤i≤N)(1≤i≤N) is denoted by AiAi.

Chef defines the function MEX(u,v)MEX(u,v) as follows:
Let BB denote the set of all the values of nodes that lie in the shortest path from uu to vv (including both uu and vv). Then, MEX(u,v)MEX(u,v) denotes the MEX of the set BB.

Find the maximum value of MEX(1,i)MEX(1,i), where 1≤i≤N1≤i≤N.

Input Format

- The first line of input contains a single integer TT, denoting the number of test cases. The description of the TT test cases follows.

- The first line of each test case contains a single integer NN — the number of nodes in the tree.

- The second line of each test case contains NN space separated integers A1,A2,…,ANA1,A2,…,AN. AiAi represents the value of the ithith node.

- The following N−1N−1 lines contain two space-separated integers XX and YY, denoting that there exists an edge between the nodes XX and YY.

Output Format

For each test case, output in a single line, the maximum value of MEX(1,i)MEX(1,i) where 1≤i≤N1≤i≤N.

Constraints

- 1≤T≤1041≤T≤104

- 1≤N≤1051≤N≤105

- 0≤Ai≤N0≤Ai≤N

- 1≤X,Y≤N1≤X,Y≤N

- Sum of NN over all test cases does not exceed 3⋅1053⋅105.

Sample Input 1

3

3

0 1 2

1 2

1 3

4

0 1 2 3

1 2

2 3

1 4

5

1 2 3 4 0

1 2

2 3

2 4

1 5

Sample Output 1

2

3

2

Explanation

Test case 11:

- MEX(1,1)=MEX({A1})=MEX({0})=1MEX(1,1)=MEX({A1})=MEX({0})=1.

- MEX(1,2)=MEX({A1,A2})=MEX({0,1})=2MEX(1,2)=MEX({A1,A2})=MEX({0,1})=2.

- MEX(1,3)=MEX({A1,A3})=MEX({0,2})=1MEX(1,3)=MEX({A1,A3})=MEX({0,2})=1.
Thus, the answer is 22.

Test case 22:

- MEX(1,1)=MEX({A1})=MEX({0})=1MEX(1,1)=MEX({A1})=MEX({0})=1.

- MEX(1,2)=MEX({A1,A2})=MEX({0,1})=2MEX(1,2)=MEX({A1,A2})=MEX({0,1})=2.

- MEX(1,3)=MEX({A1,A2,A3})=MEX({0,1,2})=3MEX(1,3)=MEX({A1,A2,A3})=MEX({0,1,2})=3.

- MEX(1,4)=MEX({A1,A4})=MEX({0,3})=1MEX(1,4)=MEX({A1,A4})=MEX({0,3})=1.
Thus, the answer is 33.

Test case 33:

- MEX(1,1)=MEX({A1})=MEX({1})=0MEX(1,1)=MEX({A1})=MEX({1})=0.

- MEX(1,2)=MEX({A1,A2})=MEX({1,2})=0MEX(1,2)=MEX({A1,A2})=MEX({1,2})=0.

- MEX(1,3)=MEX({A1,A2,A3})=MEX({1,2,3})=0MEX(1,3)=MEX({A1,A2,A3})=MEX({1,2,3})=0.

- MEX(1,4)=MEX({A1,A2,A4})=MEX({1,2,4})=0MEX(1,4)=MEX({A1,A2,A4})=MEX({1,2,4})=0.

- MEX(1,5)=MEX({A1,A5})=MEX({1,0})=2MEX(1,5)=MEX({A1,A5})=MEX({1,0})=2.
Thus, the answer is 22.

MEX on Trees SOLUTION

C++

Join our telegram group for codes.

Java

Will be Updated soon

Python

Will be Updated soon

Read More Post Here