CF2219D.MEX Replacement on Tree

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).

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 $ .

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).

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 $ .