CF1615E.Purple Crayon

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.

However, to make the game fair, Red is only allowed to color $k$ nodes of the tree. In other words, after Red's turn, at most $k$ of the nodes can be colored 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.

Note: there's no restriction on the number of nodes Blue can color, as long as he doesn't color a node that Red has already colored.

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?

两名玩家——红方与蓝方——再次展开较量，而这一次他们使用蜡笔进行游戏！这对顽皮的搭档正在破坏一棵有根树，通过为节点着色来玩他们最喜爱的游戏。

游戏规则如下：给定一棵大小为 $n$ 的有根树，根节点为节点 $1$，初始时所有节点均为白色。红方与蓝方各进行一次回合，红方先行。

在红方的回合中，他可以执行以下操作任意多次：

• 任选该有根树的一棵子树，并将该子树中所有节点染成红色。

然而，为使游戏公平，红方总共至多只能染色 $k$ 个节点。换言之，红方回合结束后，至多有 $k$ 个节点被染成红色。

随后轮到蓝方行动。蓝方可以执行以下操作任意多次：

• 任选该有根树的一棵子树，并将该子树中所有节点染成蓝色。但蓝方不得选择包含任何已被染成红色节点的子树，因为那样会使该节点变成紫色，而没人喜欢紫色蜡笔。

注意：只要不染色已被红方染红的节点，蓝方对可染色的节点总数没有限制。

两回合结束后，游戏得分按如下方式计算：设 $w$ 为白色节点数，$r$ 为红色节点数，$b$ 为蓝色节点数，则游戏得分为 $w \cdot (r - b)$。

红方希望最大化该得分，蓝方则希望最小化该得分。若双方均采取最优策略，最终游戏得分是多少？

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.

第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$1 \le k \le n$）—— 分别表示树中顶点的数量以及红色节点的最大数量。

接下来的 $n - 1$ 行描述树的边。第 $i$ 行包含两个以空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$；$u_i \neq v_i$）—— 表示树的第 $i$ 条边。

保证所给的边构成一棵树。

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

输出一个整数——当红方和蓝方均采取最优策略时的最终得分。

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

At the end of this process, nodes $2$ and $3$ are red, node $4$ is blue, and node $1$ is white. The score of the game is $1 \cdot (2 - 1) = 1$.

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.

At the end of this process, nodes $4$ and $5$ are red, and nodes $1$, $2$ and $3$ are white. The score of the game is $3 \cdot (2 - 0) = 6$.

For the third test case:

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

在第一个测试用例中，最优策略如下：

• 红方选择为节点 $2$ 和 $3$ 的子树着色。
• 蓝方选择为节点 $4$ 的子树着色。

该过程结束后，节点 $2$ 和 $3$ 为红色，节点 $4$ 为蓝色，节点 $1$ 为白色。游戏得分为 $1 \cdot (2 - 1) = 1$。

在第二个测试用例中，最优策略如下：

• 红方选择为节点 $4$ 的子树着色。这将同时为节点 $4$ 和 $5$ 着色。
• 蓝方没有任何可选操作，因此没有节点被着为蓝色。

该过程结束后，节点 $4$ 和 $5$ 为红色，节点 $1$、$2$ 和 $3$ 为白色。游戏得分为 $3 \cdot (2 - 0) = 6$。

对于第三个测试用例：

游戏得分为 $4 \cdot (2 - 1) = 4$。