Problem E

Statement
Copy Copied
Description:
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.

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$$$.