Author: | Anton Trygub |
Developer: | Stanislav Bezkorovainyi |
Editorialists: | Anton Trygub and Stanislav Bezkorovainyi |
Sort the array first. Say that a_1\le a_2 \le \dots \le a_{2n-2}.
Claim 1: If a_i> i for some , there is no valid tree at all.
Proof: Suppose that a_i > i. Obviously, this means that at most i-1 numbers don't exceed , but, from the other side, parents of nodes 2, 3, 4, 5, \dots, i+1 all have to be at most . Contradiction.
Claim 2: If a_i = i for some , the path from to has to include .
Proof: Suppose that a_i = i. Obviously, this means that at most i-1 numbers don't exceed i-1. From the other side, parents of nodes 2, 3, 4, 5, \dots, i all have to be at most i-1. Therefore, all these i-1 numbers will be used as parents for 2, 3, 4, 5, \dots, i, and therefore parents of all numbers from i+1 to will be at least . This means, that we can't get from to without coming through (suppose that is the last vertex on the path from to which is larger than , then it's parent has to be ).
Let t_1, t_2, \dots, t_m be the set of indexes for which a_x = x, with t_1 = 1. Let be the set of all numbers which appear among a_i, excluding t_j for 1\le j\le m — those are potential other vertices on the path. Obviously, there is no -path for k < m (as every path from to has to include at least m+1 nodes t_1, \dots, t_m, n). Also, there is no -path for k>m + |S|, as the total possible number of different vertices in the path doesn't exceed m + |S| + 1 (corresponding to ).
Claim 3: For m\le k \le m + |S|, the -long trees exist. Sum of weights for -perfect tree can then be computed as following: mark t_1, t_2, \dots, t_m as used, and k-m smallest elements from as used. Answer is the sum of largest of 2n-2 - k not marked numbers.
Proof: Obviously, this is the upper bound, it's left to prove that it's achievable. Denote k-m smallest elements of as s_1 < s_2 < \dots < s_{k-m}. So our path will contain vertices path_1 < path_2 < \dots < path_k < path_{k+1}, where path_1 = 1, path_{k+1} = n, and path_1, path_2, \dots, path_k is a sorted union of t_1, t_2, \dots, t_m, s_1, \dots, s_{k-m}. We now set parent of path_{i+1} to be path_i for each .
Mark first occurrences of t_1, t_2, \dots, t_m, s_1, \dots, s_{k-m} in as used. Also mark all the vertices that we've given a parent this way. There are 2n-2 - k indexes which are yet not used, let them be x_1 \le x_2 \le \dots \le x_{2n-2-k}. Now look at all the n-k-1 vertices (except for which aren't assigned a parent yet, assign a_{x_i} to the -th of them (in increasing order). After that, distribute all n-1 numbers which are left can be used as weights, use largest of them on the , and others arbitrarily. This gives the answer from the claim, we just have to prove that we have actually produced a tree.
Let v_1, v_2, \ldots, v_{n-k-1} be a sorted array of vertices which were not assigned a parent yet. Note, that vertex can not have a parent, so v_1 \neq 1. Let's iterate over array . Let's say that we want to assign a parent for vertex v_i . As said before, we want to assign parent of vertex v_i as a_{x_i}. This is valid if and only if a_{x_i} < v_i. Now we have to prove that a_{x_i} < v_i for any from to n-k-1.
Let's suppose that it is not true and for some , a_{x_i} \geq v_i. Without loss of generality, path_j \leq a_{x_i} < path_{j+1} for some . It means, that a_{x_i} is greater than or equal to the numbers of first vertices of the (i.e marked vertices) and a_{x_i} \geq v_i > v_{i-1} > \ldots > v_1 (i.e unmarked vertices). Since a_{x_i} is greater than or equal to the numbers of the first i+j vertices it means, that a_{x_i} \geq i + j.
Now let's look at value x_i. What does it mean that an element has position x_i in array ? It means that there are exactly x_i - 1 elements before it in the array.
How many unmarked positions are there before x_i? These are x_1, x_2, \ldots, x_{i-1}. And thus, there are exactly i-1 unmarked positions before x_i.
How many marked positions are there before x_i? As we already said, path_j \leq a_{x_i} < path_{j+1}. Since we marked the first occurence of path_j in the array, so path_j > path_{j-1} > \ldots > path_{1} these are all before of the position x_i. x_i < path_{j+1} < \ldots < path_{k} these all, obviously go after position x_i since array is sorted. So there are exactly marked positions before x_i.
Since every position is either marked or not marked, there are exacly i-1+j positions before x_i. So, x_i = i - 1 + j + 1 = i + j.
Quick observation. From first two claims we know that if for some a_i > i, then there is no answer and if for some a_i = i, then we have already added to out path. So, now we know that on every position that has not been marked yet a_i < i. Thus, a_{x_i} < x_i. But we have already discovered, that a_{x_i} \geq i + j and that x_i = i + j, so we get a_{x_i} \geq x_i. Contradiction.
Now let's move to the algorithmic side. We have to be able to calculate the sum of largest numbers among x_1, x_2, \dots, x_{2n-k} where k-m smallest elements of are discarded. It's the easy part: for k = m, the set of largest numbers will be just largest numbers in . Now, maintain the set of values of that are prohibited, and we haven't discarded yet. At every step, add next element of to this set, and the next (in decreasing order) x_i in the set of the largest numbers. Now, while set of largest numbers contains some that is in set to be discarded, delete one instance of from both to be discarded and largest numbers, and add a next number into the largest instead. Sum recalculation is obvious.