Parmigiana With Seafood
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 3000
Tags: binary search, dp, greedy, trees

The "Parmigiana di melanzane" is a typical Italian dish. Alessandro and Bianca have very different tastes when it comes to it: Alessandro loves to eat Parmigiana with seafood, but Bianca thinks it is an atrocity! To decide which ingredients to include in the dish they prepare, they play the following game.

There are $$$n$$$ possible ingredients, labeled from $$$1$$$ to $$$n$$$. The higher the label, the closer the ingredient is to being seafood. The ingredients are connected by $$$n - 1$$$ edges, in such a way as to form a tree. Alessandro and Bianca take turns, with Alessandro going first. They alternately choose a terminal ingredient $$$x$$$, that is an ingredient currently connected to at most one other ingredient, and remove it from the tree. If the terminal ingredient $$$x$$$ was chosen by Alessandro, it goes in the recipe; if it was chosen by Bianca, it is discarded.

The taste of the Parmigiana is measured as the maximum label of an ingredient in the recipe. Alessandro wants to maximize the taste, while Bianca wants to minimize the taste. If both play optimally, what is the taste of the Parmigiana?

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

Each of the following $$$n-1$$$ lines contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — the ingredients that the $$$i$$$-th edge connects.

It is guaranteed that the edges form a tree (i.e., any pair of ingredients is connected by the edges, possibly indirectly).

Output format:
Print the value of the taste if both Alessandro and Bianca play optimally.

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

Note:
In the first sample, Alessandro can choose terminal ingredient $$$4$$$ in the first turn. This ingredient is added to the recipe. Since $$$4$$$ is the maximum label of an ingredient, the taste is $$$4$$$ regardless of the choices that follow.

In the second sample, Bianca can make sure that neither ingredient $$$4$$$ nor $$$5$$$ are included in the recipe, in which case Alessandro can include $$$3$$$. Thus, the taste is $$$3$$$.

Example input:
4
1 2
1 3
1 4

Example output:
4

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

Example output:
3

Editorial:
First, as for many tree problem, let us solve it first on chains, then generalize the solution for trees.
Game on a path
First, start with several observations on Alessandro's strategy.
Definition (bad pair). We say that two ingredients form a bad pair if they are at odd distance of each other.
Lemma 1. Alessandro can choose the best of the following strategies:
• First, he can include any ingredient which is a terminal ingredient at the begining of the game.
• Second, if $$$n$$$ is even, then he can make sure to include ingredient $$$n$$$.
• Third, if $$$n$$$ is odd and given a bad pair, he can always make sure that one of the two ingredient is included in the recipe.
Proof. The first observation is easy as Alessandro plays first. For the second observation, Alessandro's strategy is to include ingredient $$$n$$$ whenever allowed to, and otherwise to select an ingredient which does not make $$$n$$$ a terminal. Observe that when only 3 ingredients remain, such that $$$n$$$ is the middle one, then it must be Bianca's turn, and Alessandro will be able to pick $$$n$$$ on the next turn. For the third observation, the same argument hold, and it must be Bianca's turn when the only possible moves make either $$$x$$$ or $$$y$$$ terminal. An alternative explaination is to look at all the ingredients on the path between $$$x$$$ and $$$y$$$ (including $$$x$$$ and $$$y$$$) as one very large ingredient (changing the parity of the number of items), and to apply the second observation.
Now, we have to check whether or not Alessandro can do even better, by looking at Bianca's strategy.
Lemma 2. Assuming that $$$n$$$ is odd, consider a set $$$S$$$ of non-terminal vertices which contain no bad pair of ingredients. Bianca can make sure that each ingredient of $$$S$$$ is discarded.
Proof. Bianca's strategy is (i) to select and discard ingredients from $$$S$$$ whenever possible, and (ii) to only select ingredients which do not make any ingredient of $$$S$$$ terminal. Observe that ingredients of $$$S$$$ are not adjacent and thus (i) does not contradict (ii). To prove (ii), observe that whenever it is Bianca's turn the number of remaining ingredients is even. If only two ingredient remains then at most one can be in $$$S$$$ and (ii) holds. If the chain has four or more ingredients then it has the form $$$$$$a - x - \dots - y - b$$$$$$ where $$$x$$$ and $$$y$$$ are at odd distance. In particular, either $$$x$$$ or $$$y$$$ is not is $$$S$$$, and Bianca can select and discard the corresponding neighbour and (ii) holds. Finally, we can prove by induction that whenever Alessandro plays, none of the terminal ingredients is in $$$S$$$, concluding the proof.
Game on a tree
We now move on to the same question, when the graph of ingredients is a tree. One can check that Lemma 1 still apply, with the exact same proof. However, the proof of Lemma 2 relied on the chain structure and does not hold for trees, as the following example shows.
Nodes in $$$S$$$ colored in red. If Alessandro selects either 1 or 2, then Bianca will have to make one of the red ingredients terminal. This is caused by the fact that there is an even number of ingredients between red ingredients. Equivalently, this happens because there is a bad triple, as formalized in the following Definition and Lemma.
Definition (bad triple). We say that three ingredients $$$x$$$, $$$y$$$ and $$$z$$$ form a bad triple if there exist one indredient $$$m$$$ whose removal would disconnect $$$x$$$, $$$y$$$ and $$$z$$$ ($$$m$$$ is sometimes called the median), and such that all three ingredients $$$x$$$, $$$y$$$ and $$$z$$$ are at even distance of $$$m$$$.
In the example above, ingredients $$$x=8$$$, $$$y=9$$$ and $$$z=10$$$ form a bad triple, as they are all three at distance two of their median $$$m=11$$$.
Lemma 3. If $$$n$$$ is odd and a bad triple is given, Alessandro can make sure one of the three ingredients of the triple is included in the recipe.
Proof. If one player is forced to make one of the three ingredients a terminal, then an even number of ingredient remains, and thus it is Bianca's turn to play.
Finally, we show that Alessandro cannot do better than combining strategies from Lemmas 1 and 3.
Lemma 4. Assuming that $$$n$$$ is odd, consider a set $$$S$$$ of non-terminal vertices which contain no bad pair and no bad triple of ingredients. Bianca can make sure that each ingredient of $$$S$$$ is discarded.
Proof. Once again, Bianca's strategy is (i) to select and discard ingredients from $$$S$$$ whenever possible, and (ii) to only select ingredients which do not make any ingredient of $$$S$$$ terminal. To prove that (ii) holds, one can use an induction on $$$|S|$$$, which is left as an exercise.
Therefore if both players play optimally, the largest index included by Alessandro is characterized by Lemma 1 and 3. More precisely:
• if $$$n$$$ is even then the answer is $$$n$$$,
• otherwise, it is the maximum between   the index of any terminal ingredient,  the index of any ingredient at odd distance to $$$n$$$,  $$$\min(x,y)$$$ for any bad triple $$$(x,y,n)$$$,  $$$\min(x,y,z)$$$ for any bad triple $$$(x,y,z)$$$ whose median is $$$n$$$.
• the index of any terminal ingredient,
• the index of any ingredient at odd distance to $$$n$$$,
• $$$\min(x,y)$$$ for any bad triple $$$(x,y,n)$$$,
• $$$\min(x,y,z)$$$ for any bad triple $$$(x,y,z)$$$ whose median is $$$n$$$.