Purple Crayon
Contest: Codeforces Global Round 18
Difficulty rating: 2400
Tags: data structures, dfs and similar, games, graphs, greedy, math, sortings, trees

Two players, Red and Blue, are at it again, and this time they're playing with crayons! The mischievous duo is now vandalizing a rooted tree, by coloring the nodes while playing their favorite game.

The game works as follows: there is a tree of size $$$n$$$, rooted at node $$$1$$$, where each node is initially white. Red and Blue get one turn each. Red goes first.

In Red's turn, he can do the following operation any number of times:

- Pick any subtree of the rooted tree, and color every node in the subtree red.

Then, it's Blue's turn. Blue can do the following operation any number of times:

- Pick any subtree of the rooted tree, and color every node in the subtree blue. However, he's not allowed to choose a subtree that contains a node already colored red, as that would make the node purple and no one likes purple crayon.

After the two turns, the score of the game is determined as follows: let $$$w$$$ be the number of white nodes, $$$r$$$ be the number of red nodes, and $$$b$$$ be the number of blue nodes. The score of the game is $$$w \cdot (r - b)$$$.

Red wants to maximize this score, and Blue wants to minimize it. If both players play optimally, what will the final score of the game be?

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le n$$$) — the number of vertices in the tree and the maximum number of red nodes.

Next $$$n - 1$$$ lines contains description of edges. The $$$i$$$-th line contains two space separated integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \neq v_i$$$) — the $$$i$$$-th edge of the tree.

It's guaranteed that given edges form a tree.

Output format:
Print one integer — the resulting score if both Red and Blue play optimally.

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

Note:
In the first test case, the optimal strategy is as follows:

- Red chooses to color the subtrees of nodes $$$2$$$ and $$$3$$$.
- Blue chooses to color the subtree of node $$$4$$$.

In the second test case, the optimal strategy is as follows:

- Red chooses to color the subtree of node $$$4$$$. This colors both nodes $$$4$$$ and $$$5$$$.
- Blue does not have any options, so nothing is colored blue.

For the third test case:

The score of the game is $$$4 \cdot (2 - 1) = 4$$$.

Example input:
4 2
1 2
1 3
1 4

Example output:
1

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

Example output:
6

Editorial:
After expanding the expression given in the statement (by replacing $$$w$$$ with $$$n - r - b$$$), it reduces to $$$r \cdot (n - r) - b \cdot (n - b)$$$. This means that in Blue's turn, his only goal is to maximize $$$b \cdot (n - b)$$$. To maximize the value of that function, it's optimal to pick the value of $$$b$$$ that is closest to $$$\lfloor \frac{n}{2} \rfloor$$$.
One thing to note is that if it's possible for Blue to color exactly $$$x$$$ nodes, for some number $$$x$$$, it is possible for Blue to color exactly $$$x-1$$$ nodes as well. This is because, given some subtree that he has colored, he can also choose to color every node in the subtree except the root. This would reduce the number of Blue nodes by exactly $$$1$$$. By repeating this process, one can show that if Blue can color exactly $$$x$$$ nodes, Blue can also color $$$y$$$ nodes if $$$y \leq x$$$.
What this implies is that if you know the number of nodes that Red colors, Red's optimal strategy would be to minimize the maximum number of nodes that Blue can color (as it reduces the possible choices that Blue has). If Red chooses node $$$x$$$, it means that Blue can't choose any ancestors (or descendants) of node $$$x$$$. This transforms the problem into the following:
For all $$$i \leq k$$$, perform the following operation exactly $$$i$$$ times: choose a node $$$v$$$ and mark all of the nodes on the path to the root. For each $$$i$$$, calculate the maximum number of nodes that are marked at least once at the end of this process by optimally choosing $$$v$$$ at each step. The set of optimally chosen $$$v$$$ (for a given $$$i$$$) can be found using the following greedy algorithm:
• Sort all nodes in decreasing order of depth.
• Then, go through the nodes in order, let the current node be $$$v$$$. Go to the root marking nodes until you reach one that has already been marked. Let the number of marked nodes be $$$c_v$$$.
• Finally, sort all nodes in decreasing order of $$$c_v$$$. Choose the first $$$i$$$ nodes from this list.
Proof that the greedy produces the correct answer: We must prove that the greedy algorithm always chooses a subset of nodes that maximizes the number of marked nodes at the end of the process. We can imagine that instead of coloring nodes, we can delete them from the tree to get a forest of rooted trees. Let's prove that there is an optimal solution where the deepest leaf in a forest (say $$$v$$$) is chosen. Consider a configuration in which $$$v$$$ is not chosen. Let $$$u$$$ be the node that maximizes the depth of LCA($$$u$$$, $$$v$$$) that is present in the configuration. You can replace the node $$$u$$$ with $$$v$$$ in the configuration, and the answer won't decrease (as the depth of $$$v$$$ is greater than the depth of $$$u$$$). Since the relative order of depths in a tree in the forest at any point is the same as the relative order of depths of its vertices in the original tree, choosing the deepest node in a tree in the forest is equivalent to choosing the vertex in that tree, which has the max depth in the original tree.
Note that the process can be simulated in amortized linear time (not including the sorting), as each node will be colored at most once. All that's left is to iterate over all values of $$$i$$$, and take the maximum value that Red can get.