Gastronomic Event
Contest: SWERC 2021-2022 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Tags: dp, greedy, trees

SWERC organizers want to hold a gastronomic event.

The location of the event is a building with $$$n$$$ rooms connected by $$$n-1$$$ corridors (each corridor connects two rooms) so that it is possible to go from any room to any other room.

In each room you have to set up the tasting of a typical Italian dish. You can choose from $$$n$$$ typical Italian dishes rated from $$$1$$$ to $$$n$$$ depending on how good they are ($$$n$$$ is the best possible rating). The $$$n$$$ dishes have distinct ratings.

You want to assign the $$$n$$$ dishes to the $$$n$$$ rooms so that the number of pleasing tours is maximal. A pleasing tour is a nonempty sequence of rooms so that:

- Each room in the sequence is connected to the next one in the sequence by a corridor.
- The ratings of the dishes in the rooms (in the order given by the sequence) are increasing.

Input format:
The first line contains an integer $$$n$$$ ($$$2\le n\le 1\,000\,000$$$) — the number of rooms.

The second line contains $$$n-1$$$ integers $$$p_2, p_3, \cdots , p_n$$$ ($$$1 \leq p_i < i$$$). Each $$$p_i$$$ indicates that there is a corridor between room $$$i$$$ and room $$$p_i$$$. It is guaranteed that the building has the property that it is possible to go from any room to any other room.

Output format:
Print the maximum number of pleasing tours.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first sample, it is optimal to place the dish with rating $$$1$$$ in room $$$1$$$, the dish with rating $$$2$$$ in room $$$3$$$, the dish with rating $$$3$$$ in room $$$2$$$, the dish with rating $$$4$$$ in room $$$5$$$ and the dish with rating $$$5$$$ in room $$$4$$$.

All the $$$13$$$ possible pleasing tours are: $$$(1)$$$, $$$(2)$$$, $$$(3)$$$, $$$(4)$$$, $$$(5)$$$, $$$(1,2)$$$, $$$(3,2)$$$, $$$(2,4)$$$, $$$(2,5)$$$, $$$(1,2,4)$$$, $$$(1,2,5)$$$, $$$(3,2,4)$$$, $$$(3,2,5)$$$.

There are also other ways to assign the dishes to the rooms so that there are $$$13$$$ pleasing tours.

Example input:
5
1 2 2 2

Example output:
13

Example input:
10
1 2 3 4 3 2 7 8 7

Example output:
47

Editorial:
This is a classical problem in which one must find a "simple" characterization of what the optimal solution looks like, and then restrict the search for the maximum to the (much smaller, much more regular) family of instances that satisfy the characterization.
In our specific case, the first part of this paradigm is by far the most difficult and the one that requires all the important insights, while the second part can be solved through the application of a standard technique. We are going to split the core of the solution in two parts, the first of which deals with the characterization of optimal solutions. Then, in the second, we will explain how to compute the answer efficiently in the restricted search space and we will discuss some improvements and further considerations.
Preliminary observations and notation
First, however, let us set up the bases. It goes without saying that we are dealing with a graph — actually, a tree — problem. Also, the statement is deceptively straightforward: assign a permutation of $$$\{1, \, \dots, \, n\}$$$ to the vertices so as to maximize the number of increasing paths.
And here comes the first non-trivial (however simple) idea: we are actually going to consider ways to orient the edges of the tree, and find an orientation that maximizes the number of directed paths; we forget about the vertex numeration altogether. After all, an assignment of the numbers $$$1, \, \dots, \, n$$$ naturally induces an orientation of the edges, where edge $$$(u, \, v)$$$ points towards $$$v$$$ if $$$u < v$$$ and towards $$$u$$$ otherwise. This begs the question of whether the converse is also true, i.e., does an orientation of the edges "induce" a numbering of the vertices? The answer is, in general, no. Nevertheless, we would still be happy if it were true that every orientation is induced by at least one numbering (for this would mean that, in switching to the orientation perspective, we wouldn't be considering forbidden configurations). Luckily, it is, and it follows immediately from the existence of a topological sorting of the vertices of a directed tree (which is, in fact, a DAG): just number the vertices in their topological order! (Incidentally, note that any topological order works, and since it is generally not unique, neither is the numbering.)
From now on, we shall call a path any path in the undirected tree, as opposed to directed path which refers to the underlying orientation of the edges (supposing we have fixed one in the context of the sentence). A single vertex is both a path and a directed path. Given an orientation of the tree, we call its value the number of directed paths it produces; therefore, the problem asks to maximize the value of an orientation. We say that a (directed) path has length $$$\ell$$$ if it is made up of $$$\ell$$$ vertices. Finally, we denote $$$d(u, \, v)$$$ the distance between $$$u$$$ and $$$v$$$ in the undirected tree.
Characterizing the optimal solutions
The next two results are crucial.
Lemma 1. Fix an orientation of the edges. Suppose there exist four distinct vertices $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ such that (refer to the figure below for clarity):
• there are edges $$$a \rightarrow b$$$ and $$$c \rightarrow d$$$;
• there is a directed path from $$$c$$$ to $$$b$$$.
Proof. Let's see what happens, in terms of value, when we reverse edge $$$a \rightarrow b$$$ and the subtree rooted at $$$a$$$. Let:
• $$$A$$$ be the number of directed paths (in the initial orientation) ending at $$$a$$$, including the path of length $$$1$$$;
• $$$B_{\mathrm{out}}$$$ be the number of directed paths of length $$$\ge 2$$$ starting at $$$b$$$;
• $$$B_{\mathrm{in}}$$$ be the number of directed paths of length $$$\ge 2$$$ ending at $$$b$$$ that do not go through edge $$$a \rightarrow b$$$.
With similar reasoning and notation, if we invert the edge $$$c \rightarrow d$$$ and the subtree rooted at $$$d$$$, the vaue increases (or decreased) by $$$\Delta_2 = D(C_{\mathrm{out}} - C_{\mathrm{in}})$$$. Now, since every directed path beginning at $$$b$$$ can be extended to the left until we get to $$$c$$$ (i.e. we can pre-append the path $$$c \rightarrow \cdots \rightarrow b$$$), and since $$$c \rightarrow \cdots \rightarrow b$$$ is itself a path beginning at $$$c$$$, it holds $$$C_{\mathrm{out}} \ge B_{\mathrm{out}} + 1$$$. Likewise, we can prove $$$B_{\mathrm{in}} \ge C_{\mathrm{in}} + 1$$$. Thus, $$$(B_{\mathrm{in}} - B_{\mathrm{out}}) + (C_{\mathrm{out}} - C_{\mathrm{in}}) \ge 2$$$ and without loss of generality $$$B_{\mathrm{in}} - B_{\mathrm{out}} > 0$$$, which implies, since $$$A > 0$$$, that $$$\Delta_1 > 0$$$ as desired. $$$\blacksquare$$$
From Lemma 1 it follows that, in an orientation that yields the optimal solution, every path "changes direction" at most once. Formally: given a path $$$(v_1, \, v_2, \, \dots, \, v_k)$$$, there exists at most one index $$$2 \le i \le k - 1$$$ such that the path $$$(v_{i - 1}, \, v_i, \, v_{i + 1})$$$ is not directed. This condition is equivalent to a very simple property which opens up the way to an efficient algorithm to find the solution.
Lemma 2. Suppose a directed tree satisfies the aforementioned condition. Then, there exists a (not necessarily unique) vertex $$$v^*$$$ such that all paths having $$$v^*$$$ as an endpoint are also directed paths.
Proof. We shall start by fixing an arbitrary vertex $$$v$$$ and rooting the tree at $$$v$$$. Call a vertex $$$u \ne v$$$ evil if it has a child $$$w$$$ such that the path $$$(v, \, \dots, \, u, \, w)$$$ changes direction at $$$u$$$. If there are no evil vertices, $$$v$$$ is a valid candidate for $$$v^*$$$ and we are done.
Otherwise, all evil vertices must lie in the same $$$v$$$-subtree. Indeed, if $$$u$$$ and $$$u'$$$ were two evil vertices belonging to different subtrees, and $$$w$$$, $$$w'$$$ the respective children, the path $$$(w, \, u, \, \dots, \, v, \, \dots, \, u', \, w')$$$ would change direction at least twice (see figure below, (a)). Moreover, if $$$u$$$ is an evil vertex and $$$r$$$ is the root of its subtree, the edge $$$(v, \, r)$$$ must point in a different direction than all other edges incident on $$$v$$$. To see why, suppose without loss of generality $$$v \rightarrow r$$$ and $$$v \rightarrow r' \ne r$$$; then the path $$$(w, \, u, \, \dots, \, r, \, v, \, r')$$$ changes direction twice (see figure below, (b)).
Thanks to the previous observations, if we replace $$$v$$$ with $$$r$$$ the set of evil vertices decreases or stays the same. If we repeat this argument while there are evil vertices, we will produce a downward path in the tree rooted at $$$v$$$, which must stop eventually, at which point the number of evil vertices must vanish. $$$\blacksquare$$$
Thanks to Lemmas 1 and 2 combined, we know that any optimal orientation admits the existence of a vertex $$$v^*$$$ satisfying the property of Lemma 2. This makes us finally able to tackle the problem algorithmically.
Computing the maximum
Call a vertex $$$v^*$$$ that satisfies the property of Lemma 2 a crossroad. We are going to iterate over all $$$n$$$ vertices and find the maximum value of an orientation where said vertex is a crossroad.
Thus, fix a vertex $$$v^*$$$ and consider the $$$\deg(v^*)$$$ subtrees the tree gets split into if we erase $$$v^*$$$. In an optimal orientation, in each subtree all edges point either "inwards" or "outwards": let $$$S$$$ be the sum of the sizes of subtrees of the first kind, and $$$T$$$ be the sum of the sizes of the subtrees of the second kind. Of course, $$$S + T = n - 1$$$. Let's calculate the value of such an orientation.
• There are $$$n$$$ directed paths having $$$v^*$$$ as an endpoint.
• The directed paths lying entirely in one subtree are $$$\displaystyle \sum_{v \ne v^*} d(v^*, \, v)$$$.
• Finally, the paths starting in a subtree of the first kind and ending in a subtree of the second kind contribute with an additional $$$S \cdot T$$$ term.
Observe that the first two terms are independent of $$$S$$$ and $$$T$$$. It is trivial to compute the sizes of the subtrees in $$$\mathcal O(\deg(v^*))$$$ after preprocessing. Furthermore, the sum of distances can be updated in $$$\mathcal O(1)$$$ when moving from $$$v^*$$$ to one of its neighbors. As for the third term, it is clear that it is maximized when $$$S$$$ and $$$T$$$ are as close as possible to $$$\frac{n - 1}{2}$$$. If one of the subtrees has size $$$k \ge \frac{n}{2}$$$ (there can only be one of those), the way of doing so is trivial: just orient the edges of the big subtree one way, and all other edges the other way, so that $$$ST = k(n - 1 - k)$$$.
The matter is more complicated if all subtrees have sizes smaller than $$$\frac{n}{2}$$$. In this case, $$$v^*$$$ is a centroid of the tree. Recall that any tree has exactly one or two centroids — and the latter can only occur if $$$n$$$ is even. What we are dealing with is an instance of the knapsack problem: we are given positive integers $$$k_1, \, \dots, \, k_{\deg(v^*)}$$$ — the sizes of the subtrees — whose sum is $$$n - 1$$$, and we shall find a subset whose sum is as close as possible to $$$\frac{n - 1}{2}$$$. The naïve dynamic programming solution runs in $$$\mathcal O(n^2)$$$ at worst (with $$$\mathcal O(n)$$$ space), way too slow for our purposes. We can optimize the runtime, reducing it by a factor $$$32$$$, via the use of bitsets. This is still not enough. There is a standard, yet somewhat advanced, trick to speed the algorithm up to $$$\mathcal O\left(\frac{n\sqrt{n}}{\mathrm{sizeof}(\mathrm{int})}\right)$$$. We won't go over it here, but you can find a complete tutorial in this Codeforces blog entry (under Subset Sum Speedup 1), together with a number of other interesting related techniques. Since we only need to run this algorithm at most twice, this final optimization, carefully implemented, does the trick.
Finally, let's comment further on the nature of the characterization. So far, we know very little about the crossroad $$$v^*$$$, but intuitively it makes sense that it should be "in the middle" of the tree in order to yield an optimal solution.
Lemma 3. There is an optimal solution where at least one centroid of the tree is a crossroad.
Proof. Consider an optimal orientation where a vertex $$$v^*$$$, which is not a centroid, is a crossroad. Let $$$\tau$$$ be the subtree of size $$$\ge \frac{n}{2}$$$. We have already observed that all edges of $$$\tau$$$ must point (WLOG) toward $$$v^*$$$, and all other edges away from $$$v^*$$$. Now let $$$v$$$ be the neighbor of $$$v^*$$$ belonging to $$$\tau$$$. If we make $$$v$$$ a crossroad, by inverting edge $$$v \rightarrow v^*$$$ and keeping the orientations of all other edges, a simple computation shows that the value of the new configuration has not decreased. We can therefore iterate until we reach a centroid. $$$\blacksquare$$$
Although this result is not necessary to solve the problem, it is relatively easy to guess and prove, and it simplifies the implementation. One can even prove this slightly stronger conclusion: for each centroid, there is an optimal orientation in which it is a crossroad.
[It was briefly considered whether to give this problem with $$$n \le 10^7$$$. It turns out that the "slow" part of the algorithm is not the optimized knapsack, but rather the tree traversal needed to find the centroid. To fit the new constraint, one must come up with a way to do this without any traversal. Taking a look at the input format might be a good starting point...]