← 返回题目列表

Codeforces · 1615/E

E. 紫色蜡笔

中文机器翻译题面 查看原题

红和蓝两个玩家又开始玩了,这次他们玩的是蜡笔!这对淘气的二人组现在正在玩他们最喜欢的游戏,通过给节点着色来破坏一棵有根的树。

游戏的工作原理如下:有一棵大小为 $$$n$$$ 的树,根节点为 $$$1$$$,其中每个节点最初都是白色的。红色和蓝色各轮一回合。红色先行。

在红方的回合中,他可以执行任意次数的以下操作:

- 选择有根树的任意子树,并将子树中的每个节点着色为红色。

然后,轮到Blue了。蓝色可以执行以下操作任意多次:

- 选择有根树的任意子树,并将子树中的每个节点着色为蓝色。但是,他不允许选择包含已经染成红色的节点的子树,因为这会使该节点变成紫色,而且没有人喜欢紫色蜡笔。

两回合后,游戏得分确定如下:令$$$w$$$为白色节点的数量,$$$r$$$为红色节点的数量,$$$b$$$为蓝色节点的数量。游戏得分为$$$w \cdot (r - b)$$$。

红色想要最大化这个分数,而蓝色想要最小化它。如果双方都发挥最佳,比赛的最终比分会是多少?

输入

第一行包含两个整数 $$$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$$$ 边。

保证给定的边形成一棵树。

输出

打印一个整数 - 如果红色和蓝色都发挥最佳效果,则得到分数。

示例

输入 #1

4 2
1 2
1 3
1 4

输出 #1

1

输入 #2

5 2
1 2
2 3
3 4
4 5

输出 #2

6

输入 #3

7 2
1 2
1 3
4 2
3 5
6 3
6 7

输出 #3

4

输入#4

4 1
1 2
1 3
1 4

输出#4

-1

注意

第一个测试用例中,最优策略如下:

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

在第二个测试用例中,最优策略如下:

- 红色选择为节点 $$$4$$$ 的子树着色。这为节点 $$$4$$$ 和 $$$5$$$ 着色。
- 蓝色没有任何选项,因此没有任何颜色是蓝色的。

对于第三个测试用例:

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