Redundant Routes
Contest: Pinely Round 2 (Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: constructive algorithms, dp, trees

You are given a tree with $$$n$$$ vertices labeled $$$1, 2, \ldots, n$$$. The length of a simple path in the tree is the number of vertices in it.

You are to select a set of simple paths of length at least $$$2$$$ each, but you cannot simultaneously select two distinct paths contained one in another. Find the largest possible size of such a set.

Formally, a set $$$S$$$ of vertices is called a route if it contains at least two vertices and coincides with the set of vertices of a simple path in the tree. A collection of distinct routes is called a timetable. A route $$$S$$$ in a timetable $$$T$$$ is called redundant if there is a different route $$$S' \in T$$$ such that $$$S \subset S'$$$. A timetable is called efficient if it contains no redundant routes. Find the largest possible number of routes in an efficient timetable.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 3000$$$).

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — the numbers of vertices connected by the $$$i$$$-th edge.

It is guaranteed that the given edges form a tree.

Output format:
Print a single integer — the answer to the problem.

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

Note:
In the first example, possible efficient timetables are $$$\{\{1, 2\}, \{1, 3\}, \{1, 4\}\}$$$ and $$$\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}\}$$$.

In the second example, we can choose $$$\{ \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$$$.

Example input:
4
1 2
1 3
1 4

Example output:
3

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

Example output:
7

Editorial:
Let's call two paths adjacent if one can be obtained from the other by adding an edge to one end and removing an edge from the other end.
Proposition. There exists an optimal solution in which each pair of adjacent paths is either simultaneously chosen or simultaneously not chosen.
Proof. Consider an optimal solution that maximizes the total length of paths in it. Let's assume that in such a solution, we have taken some path $$$ab$$$, but its adjacent path $$$cd$$$ is not included (here, assume $$$a \not\in cd$$$ and $$$d \not\in ab$$$). Why can't we add $$$cd$$$?
• If $$$cd$$$ contains a shorter path, it must end at $$$d$$$ (since all other paths are also contained in $$$ab$$$). In that case, we can extend the shorter path $$$ed$$$ to $$$cd$$$, which contradicts the maximization of the sum of lengths.
• If $$$cd$$$ is contained within a longer path, it must start at $$$c$$$ (since all other paths are also contained in $$$ab$$$). In this case, we can extend $$$ab$$$.
In the rooted tree, we'll call a class vertical if it contains at least one vertical path. To reduce the number of vertical classes, we'll root the tree by the midpoint of its diameter (if the diameter is of odd length, consider the root as an edge). Now, all vertical paths of the same length are equivalent (since a vertical path can always be moved to another subtree of the root). Thus, for each length, there is at most one vertical class.
How do we determine if a path belongs to some vertical class? We'll attempt to greedily pull the path: first lower one end of the path to the deepest available vertex, then the other end, and so on. In the end, either the path becomes vertical or we encounter an obstacle of the following form: the endpoints are in non-intersecting subtrees of the same depth $$$h$$$, whose roots are at distance $$$d$$$ apart, and the path length is $$$h + d$$$. Moreover, any such pair of subtrees describes a non-vertical class of paths, and no other classes exist, as paths from a non-vertical class must hit such an obstacle.
Note. A class doesn't necessarily consist of all paths between subtrees of length $$$h + d$$$. This is because an obstacle might exist lower down for some of these paths. Nonetheless, at least one representative for any pair of subtrees will definitely exist (for instance, the root of one subtree and the deepest leaf of the other).
Let's define non-vertical classes with a pair of root vertices of subtrees $$$(v, u)$$$ (with the convention $$$tin(v) < tin(u)$$$), and define the class length as $$$L(v, u) = h + d$$$. We'll introduce a forest structure on non-vertical classes: a pair $$$(v, u)$$$ is an ancestor of $$$(v', u')$$$ if $$$v$$$ is an ancestor of $$$v'$$$ and $$$u$$$ is an ancestor of $$$u'$$$. All classes, together with this forest, can be constructed using DFS in $$$O(n^2)$$$ time, simultaneously traversing $$$v$$$ and $$$u$$$. Moreover, we can quickly compute the size of each such class. Let $$$S(v, u)$$$ denote the number of all paths of length $$$L(v, u)$$$ between subtrees $$$v$$$ and $$$u$$$. Then, the size of class $$$N(v, u)$$$ is $$$S(v, u) - \sum_{(v', u')} N(v', u')$$$, where the summation is over all classes $$$(v', u')$$$ that are proper descendants of $$$(v, u)$$$ such that $$$L(v', u') = L(v, u)$$$. Thus, we need to compute all $$$S(v, u)$$$. If we compute this for each class in $$$O(h)$$$ time, the total time will be $$$O(n^2)$$$ (exercise for the reader).
Which non-vertical classes can't be taken simultaneously? If between classes $$$a = (v, u)$$$ and $$$b = (v', u')$$$ neither is an ancestor of the other, then nested paths can't exist in them (due to the construction of the forest, there's a branching somewhere that's common to all paths).
Proposition. Let class $$$a$$$ be an ancestor of class $$$b$$$. Then, a pair of nested paths between them can exist if and only if for all classes $$$c$$$ on the path between $$$a$$$ and $$$b$$$ (including $$$b$$$ but excluding $$$a$$$), $$$L(c) > L(a)$$$.
Proof. Paths within $$$b$$$ cannot come out of subtrees $$$v', u'$$$. If $$$L(a) \leq L(b)$$$, then a path of length $$$L(a)$$$ containing something from $$$b$$$ must also go between subtrees $$$v', u'$$$, but it can't extend beyond subtrees $$$v, u$$$ (since shorter paths from $$$b$$$ can't). Thus, it can't belong to $$$a$$$. Otherwise, if we attempt to pull a path of length $$$L(a)$$$ nested within $$$b$$$ upwards until encountering an obstacle at $$$a$$$, this can only happen if $$$a$$$ is the first significant obstacle.
How do we include vertical classes? Clearly, we can take at most one vertical class. Using similar reasoning as above, if $$$a$$$ is a non-vertical class and $$$\ell$$$ is the length of a vertical class, then $$$a$$$ can be taken with a vertical class if there are no classes $$$c$$$ among the ancestors of $$$a$$$ (including $$$a$$$) with $$$L(c) \leq \ell$$$. Constructing a bamboo structure out of all vertical classes (shorter classes on top) and attaching the roots from the forest of non-vertical classes at the bottom of this bamboo, the criterion remains the same as in the proposition. Now we can forget about the original problem and solve a new one: given a rooted tree, with numbers $$$L_v$$$ and $$$N_v$$$ assigned to each vertex, we need to select a set of vertices to maximize the sum of $$$N_v$$$, while satisfying the criterion.
Consider the vertex $$$v$$$ with the minimum $$$L_v$$$ among all vertices (considering the deepest among such vertices, if there are several options). It's easy to see that:
• Vertices outside the subtree rooted at $$$v$$$ cannot prevent us from choosing vertices within the subtree rooted at $$$v$$$.
• If we choose $$$v$$$, we can't choose anything else in its subtree.
Divide the set of all vertices $$$V$$$ into $$$T_v - v$$$ and $$$V - T_v$$$, where $$$T_v$$$ is the subtree rooted at $$$v$$$, and solve the problem independently for them. The final answer will be $$$ans(V - T_v) + \max(N_v, ans(T_v))$$$.
This process can be conveniently done in reverse, for instance, using DSU. It's also possible to carefully determine, during the forest construction, which components will merge, and solve the problem in $$$O(n^2)$$$ time using just bucket sort without any additional data structures or sorting.