红和蓝两个玩家又开始玩了,这次他们玩的是蜡笔!这对淘气的二人组现在正在玩他们最喜欢的游戏,通过给节点着色来破坏一棵有根的树。
游戏的工作原理如下:有一棵大小为 $$$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$$$。