D. MEX Replacement on Tree
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree rooted at $$$1$$$ with $$$n$$$ vertices and a permutation $$$p$$$ of length $$$n$$$ consisting of integers $$$0, 1, \ldots, n - 1$$$, where $$$p_v$$$ represents the weight of vertex $$$v$$$.

Let $$$S_v$$$ denote the set of weights written on the vertices belonging to the path from $$$1$$$ to $$$v$$$. Define a function $$$f$$$ as $$$f(v) = \mathrm{MEX}(S_v)$$$, that is, the $$$\mathrm{MEX}$$$ over the set consisting of the weights of vertices on the simple path between the root and $$$v$$$ (inclusive), where $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Also, given the following operation:

  • Choose an integer $$$v$$$ ($$$1 \leq v \leq n$$$) and assign $$$f(v)$$$ to $$$p_v$$$.

Your goal is to find the maximum value of $$$\sum\limits_{v = 1}^n f(v)$$$ after performing the above operation no more than once (possibly zero).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of vertices of the tree.

The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$0 \le p_i \le n - 1$$$) — the elements of array $$$p$$$. It is guaranteed that every integer from $$$0$$$ to $$$n - 1$$$ appears exactly once in $$$p$$$.

Then $$$n - 1$$$ lines follow, each line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), indicating an edge between vertices $$$x_i$$$ and $$$y_i$$$. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single line containing an integer: the maximum value of $$$\sum\limits_{v = 1}^n f(v)$$$ after performing the above operation no more than once (possibly zero).

Example
Input
7
1
0
3
1 0 2
1 2
1 3
6
1 4 5 2 0 3
1 4
1 5
6 2
2 5
2 3
5
1 2 3 0 4
1 2
2 3
3 4
4 5
10
9 8 7 1 3 2 5 4 6 0
6 10
3 1
8 7
4 2
2 8
7 5
10 9
3 9
6 4
9
8 4 0 6 5 7 3 1 2
8 3
4 2
4 6
9 3
7 6
1 5
8 5
9 2
7
1 5 2 3 6 0 4
7 6
4 3
7 2
5 1
2 4
6 5
Output
1
4
12
9
30
26
17
Note

In the first example, not doing any operation is optimal, so the answer is $$$1$$$.

In the second example, we have

  • $$$f(1) = \mathrm{MEX}(\{p_1\}) = \mathrm{MEX}(\{1\}) = 0$$$
  • $$$f(2) = \mathrm{MEX}(\{p_1, p_2\}) = \mathrm{MEX}(\{1, 0\}) = 2$$$
  • $$$f(3) = \mathrm{MEX}(\{p_1, p_3\}) = \mathrm{MEX}(\{1, 2\}) = 0$$$

And we have the following options:

  1. Doing nothing would lead to $$$\sum\limits_{v = 1}^n f(v) = 2$$$
  2. Doing operation on vertex $$$1$$$ would assign $$$f(1) = 0$$$ to $$$p_1$$$, change $$$f(1), f(2), f(3)$$$ to $$$1$$$, which leads to $$$\sum\limits_{v = 1}^n f(v) = 3$$$
  3. Doing operation on vertex $$$2$$$ would assign $$$f(2) = 2$$$ to $$$p_2$$$, change $$$f(2)$$$ to $$$0$$$, which leads to $$$\sum\limits_{v = 1}^n f(v) = 0$$$
  4. Doing operation on vertex $$$3$$$ would assign $$$f(3) = 0$$$ to $$$p_3$$$, change $$$f(3)$$$ to $$$2$$$, which leads to $$$\sum\limits_{v = 1}^n f(v) = 4$$$

So the answer is $$$4$$$, by doing operation on vertex $$$3$$$.