utils/scrapers/prescraped/codeforces/Editorials/1981F

Idea: yinhee  Developed by 44mhq and zltzlt.  Thanks AFewSuns and razy_sea for discovering Solution 2, which runs faster than Solution 1!
**Hint 1**
Try some dp that takes $$$O(n^2)$$$ time.
**Hint 2**
What's the maximum MEX in the optimal good set of paths?
**Solution 1**
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:
 If $$$u$$$ is a leaf, then:

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

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

Expanding, we get:

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:

Hence:

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:

By fixing $$$n$$$, we can binary search for the largest $$$t$$$ satisfying the above condition, and for $$$n = 25000$$$, we find $$$t = 3863$$$.
**Solution 2**
Read the $$$O(n^2)$$$ part of Solution 1 first.
Consider using a segment tree to maintain the dp values. The transitions for $$$u$$$ with at most one child are easy to maintain, so we only need to consider the case with two children.
First, use a segment tree to maintain the minimum value of $$$f_{u,i} + i$$$, so $$$\text{minx}$$$ and $$$\text{miny}$$$ can be computed. The value of $$$f_{u,a_u}$$$ can be set to $$$+\infty$$$ by a point update.
Ignoring how to compute $$$k$$$ for now, in the end, all $$$f_{x,i}$$$ are incremented by $$$\text{miny}$$$, all $$$f_{y,i}$$$ are incremented by $$$\text{minx}$$$, and the segment trees are merged. Finally, all $$$f_{u,i}$$$ are taken as the minimum with $$$k$$$.
To compute $$$k$$$, which is $$$\min\limits_{i \neq a_u} (f_{x,i} + f_{y,i} + i)$$$, we can use a similar segment tree merging method, quickly computing this as we recursively descend to the leaf nodes of the segment tree. Additionally, we need to maintain the minimum value of $$$f_{u,i}$$$.
Time complexity: $$$\mathcal{O}(n \log n)$$$ per test case.