Turtle and Paths on a Tree
Contest: Codeforces Round 949 (Div. 2)
Difficulty rating: 3000
Tags: data structures, dp, trees

Note the unusual definition of $$$\text{MEX}$$$ in this problem.

Piggy gave Turtle a binary tree$$$^{\dagger}$$$ with $$$n$$$ vertices and a sequence $$$a_1, a_2, \ldots, a_n$$$ on his birthday. The binary tree is rooted at vertex $$$1$$$.

If a set of paths $$$P = \{(x_i, y_i)\}$$$ in the tree covers each edge exactly once, then Turtle will think that the set of paths is good. Note that a good set of paths can cover a vertex twice or more.

Turtle defines the value of a set of paths as $$$\sum\limits_{(x, y) \in P} f(x, y)$$$, where $$$f(x, y)$$$ denotes the $$$\text{MEX}^{\ddagger}$$$ of all $$$a_u$$$ such that vertex $$$u$$$ is on the simple path from $$$x$$$ to $$$y$$$ in the tree (including the starting vertex $$$x$$$ and the ending vertex $$$y$$$).

Turtle wonders the minimum value over all good sets of paths. Please help him calculate the answer!

$$$^{\dagger}$$$A binary tree is a tree where every non-leaf vertex has at most $$$2$$$ sons.

$$$^{\ddagger}\text{MEX}$$$ of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest positive integer $$$x$$$ which does not occur in the collection $$$c$$$. For example, $$$\text{MEX}$$$ of $$$[3, 3, 1, 4]$$$ is $$$2$$$, $$$\text{MEX}$$$ of $$$[2, 3]$$$ is $$$1$$$.

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

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

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the sequence $$$a$$$.

The third line of each test case contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \le p_i < i$$$) — the parent of each vertex in the tree.

Additional constraint on the input: the given tree is a binary tree, that is, every non-leaf vertex has at most $$$2$$$ sons.

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

Output format:
For each test case, output a single integer — the minimum value over all good sets of paths.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Note:
In the first test case, the tree is as follows. The number in brackets denotes the weight of the vertex:

The good set of paths with the minimum value is $$$\{(2, 3), (4, 5)\}$$$.

Note that in this test case $$$\{(4, 5)\}$$$ and $$$\{(3, 4), (4, 5)\}$$$ are not good sets of paths because each edge should be covered exactly once.

In the second test case, the tree is as follows:

The set of good paths with the minimum value is $$$\{(1, 2), (1, 3), (4, 5)\}$$$.

In the third test case, the tree is as follows:

The set of good paths with the minimum value is $$$\{(1, 6), (3, 5)\}$$$.

Example input:
5
5
3 2 2 1 1
1 1 2 2
5
3 2 1 1 1
1 1 2 2
6
1 2 1 2 1 3
1 2 3 3 4
7
2 1 2 3 1 2 1
1 1 2 2 3 3
10
1 2 2 1 4 2 3 1 2 1
1 1 2 2 3 3 4 5 5

Example output:
4
6
6
6
7

Editorial:
Let's consider dp. Let $$$f_{u, i}$$$ denote the path extending upward within the subtree rooted at $$$u$$$, with the condition that this path does not include the value $$$i$$$. The value of $$$i$$$ ranges from $$$[1, n + 1]$$$. In this case, we can directly take the MEX of this path as $$$i$$$, because if the MEX is not $$$i$$$, then the MEX will be smaller, making this dp state suboptimal.
Let $$$f_{u,i}$$$ denote the minimum result of the $$$\operatorname{MEX}$$$ of a path that extends outside the subtree of $$$u$$$ and is specified to be $$$i$$$ (where $$$i$$$ is not included in the result). Since the $$$\operatorname{MEX}$$$ of each path does not exceed $$$n+1$$$, the values of $$$i$$$ range from $$$1$$$ to $$$n+1$$$.
Consider all the transitions for the dp:
1. If $$$u$$$ is a leaf, then:$$$$$$ f_{u,i} = \begin{cases} 0, & i \neq a_u \\ +\infty, & i = a_u \end{cases} $$$$$$
2. If $$$u$$$ has only one child, let the child be $$$x$$$. Let $$$\text{minx} = \min\limits_{i \neq a_u} (f_{x,i} + i)$$$, then: $$$$$$ f_{u,i} = \begin{cases} \min(f_{x,i}, \text{minx}), & i \neq a_u \\ +\infty, & i = a_u \end{cases} $$$$$$
3. If $$$u$$$ has two children, let the children be $$$x$$$ and $$$y$$$. Let $$$\text{minx} = \min\limits_{i \neq a_u} (f_{x,i} + i)$$$ and $$$\text{miny} = \min\limits_{i \neq a_u} (f_{y,i} + i)$$$. There are four possible transitions:  Continuing the path from the subtree of $$$x$$$, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, f_{x,i} + \text{miny})$$$  Continuing the path from the subtree of $$$y$$$, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, f_{y,i} + \text{minx})$$$  Creating a new path and merging the paths from both subtrees, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, \min\limits_{j \neq a_u} (f_{x,j} + f_{y,j} + j))$$$  Creating a new path without merging the paths from the two subtrees, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, \text{minx} + \text{miny})$$$ Let $$$k = \min(\min\limits_{i \neq a_u} (f_{x,i} + f_{y,i} + i), \text{minx} + \text{miny})$$$, then the transition can be written as follows: $$$$$$ f_{u,i} = \begin{cases} \min(f_{x,i} + \text{miny}, f_{y,i} + \text{minx}, k), & i \neq a_u \\ +\infty, & i = a_u \end{cases} $$$$$$
4. Continuing the path from the subtree of $$$x$$$, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, f_{x,i} + \text{miny})$$$
5. Continuing the path from the subtree of $$$y$$$, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, f_{y,i} + \text{minx})$$$
6. Creating a new path and merging the paths from both subtrees, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, \min\limits_{j \neq a_u} (f_{x,j} + f_{y,j} + j))$$$
7. Creating a new path without merging the paths from the two subtrees, i.e., $$$\forall i \neq a_u, f_{u,i} = \min(f_{u,i}, \text{minx} + \text{miny})$$$
This results in a time complexity of $$$O(n^2)$$$.
In fact, we can prove that we only need to consider MEX values up to $$$O(\frac{n}{\ln n})$$$ (for $$$n = 25000$$$, we only need to consider MEX values up to $$$3863$$$). Therefore, the second dimension of the dp only needs to be enumerated up to $$$O(\frac{n}{\ln n})$$$ (or $$$3863$$$).
Also, we have a construction of a chain that can achieve the MEX value of $$$O(\frac{n}{\ln n})$$$, which is enumerating $$$i$$$ from $$$1$$$ and listing all the divisors of $$$i$$$ in descending order, such as $$$[1, 2, 1, 3, 1, 4, 2, 1, 5, 1]$$$.
Time complexity: $$$O(\frac{n^2}{\ln n})$$$ per test case.
Proof of the upper bound for MEX:
Let's only consider the case of a chain. For a fixed $$$x$$$, consider a sequence like $$$[a, \ldots, b, x, c, \ldots, d, x, e, \ldots, f, x, g, \ldots, h]$$$. We can divide it into segments as follows:
$$$$$$[a, \ldots, b], [b, x, c], [c, \ldots, d], [d, x, e], [e, \ldots, f], [f, x, g], [g, \ldots, h]$$$$$$
Where segments without $$$x$$$ have a MEX value $$$\le x$$$, and segments with $$$x$$$ have a MEX value $$$\le 4$$$.
Let $$$t$$$ be the answer. Then, $$$t$$$ satisfies: (where $$$c_i$$$ is the number of occurrences of $$$i$$$)
$$$$$$\min_{i \ge 1} (c_i + 1) i + 4 c_i \ge t$$$$$$
Expanding, we get:
$$$$$$\min_{i \ge 1} (c_i + 1) (i + 4) \ge t$$$$$$
Furthermore, for segments like $$$[b, x, c]$$$, if $$$x \ge 4$$$, then the term $$$4c_i$$$ above can be reduced to $$$3c_i$$$ (since $$$x$$$ can be none of $$$1, 2, 3$$$). So, we have:
$$$$$$\min(\min_{i = 1}^3 (c_i + 1)(i + 4), \min_{i \ge 4}(c_i + 1)(i + 3)) \ge t$$$$$$
Hence:
$$$$$$c_i \ge \begin{cases} \left\lceil\frac{t}{i + 4}\right\rceil - 1 & 1 \le i \le 3 \\ \left\lceil\frac{t}{i + 3}\right\rceil - 1 & i \ge 4 \end{cases}$$$$$$
This means we need $$$O(\frac{t}{i})$$$ occurrences of $$$i$$$, and since $$$n = O(t \ln t)$$$, we have $$$t = O(\frac{n}{\ln n})$$$.
We also have:
$$$$$$n = \sum_{i \ge 1} c_i \ge \sum_{i = 1}^3 (\left\lceil\frac{t}{i + 4}\right\rceil - 1) + \sum_{i \ge 4} (\left\lceil\frac{t}{i + 3}\right\rceil - 1)$$$$$$
By fixing $$$n$$$, we can binary search for the largest $$$t$$$ satisfying the above condition, and for $$$n = 25000$$$, we find $$$t = 3863$$$.