MEX on Trees

 Consider a tree with 

N$N$ nodes, rooted at node 1$1$.
The value of the ith$i^{th}$ node (1≤i≤N)$(1\le i\le N)$ is denoted by Ai$A_i$.

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

Find the maximum value of MEX(1,i)$MEX(1,i)$, where 1≤i≤N$1\le i\le N$.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of the T$T$ test cases follows.
• The first line of each test case contains a single integer N$N$ - the number of nodes in the tree.
• The second line of each test case contains N$N$ space separated integers A1,A2,...,AN$A_1,A_2,...,A_N$. Ai$A_i$ represents the value of the ith$i^{th}$ node.
• The following N−1$N-1$ lines contain two space-separated integers X$X$ and Y$Y$, denoting that there exists an edge between the nodes X$X$ and Y$Y$.

Output Format

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

Constraints

• 1≤T≤104$1\le T\le {10}^4$
• 1≤N≤105$1\le N\le {10}^5$
• 0≤Ai≤N$0\le A_i\le N$
• 1≤X,Y≤N$1\le X,Y\le N$
• Sum of N$N$ over all test cases does not exceed 3⋅105$3\cdot {10}^5$.

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 1$1$:

• MEX(1,1)=MEX({A1})=MEX({0})=1
  
• MEX(1,2)=MEX({A1,A2})=MEX({0,1})=2.
• MEX(1,3)=MEX({A1,A3})=MEX({0,2})=1$1$.
  Thus, the answer is 2$2$.

Test case 2$2$:

• MEX(1,1)=MEX({A1})=MEX({0})=1$M$
• MEX(1,2)=MEX({A1,A2})=MEX({0,1})=2.
• $1$.
  Thus, the answer is 3$3$.

Test case 3$3$:

• MEX(1,1)=MEX({A1})=MEX({1})=0
  
• MEX(1,2)=MEX({A1,A2})=MEX({1,2})=0.
• $0$.
• $1,0\})=2$.
  Thus, the answer is 2$2$.

• Tweet
• Share
• Share
• Share
• Share

Related Post