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