Description

:::align{center}

:::

新晋市场的零售商 YAOGS（Yet Another Olympic Goodies Seller）正在销售非常昂贵的奥运主题商品。为了提升知名度，他们决定半心半意地通过一场竞赛赠送部分商品：第一个正确回答“奥运会标志中有多少个圆环？”的人，可以获得最多 $P$ 件价值相等且非常昂贵的商品。

为了增加趣味性（以及减少开支），YAOGS 还设置了额外的挑战。$P$ 件商品被放置在 YAOGS 总部的一些（但不一定全部）走廊上；每条走廊可以放置 0 件、1 件或多件商品。出于未知原因，这些走廊构成了一棵连通、无向、无环的图（即一棵树），共有 $N$ 个节点，编号从 $0$ 到 $N-1$。

获胜者知道 $N$，但对树的结构和商品的具体分布一无所知。商品放置完毕后，她需要选择一个起点节点 $m$ 和一个终点节点 $n$。然后，她可以收集从 $m$ 到 $n$ 的树上（唯一）路径上的所有商品。

YAOGS 会巧妙地放置商品，使得获胜者无论如何都无法收集到太多商品。假设 YAOGS 做到了最优放置，请问获胜者最多能收集到多少件商品？

Input Format

每行包含两个用空格分隔的整数。第一行包含两个整数 $N$ 和 $P$。接下来的 $N-1$ 行，每行包含两个整数 $a_k$ 和 $b_k$，表示在树中节点 $a_k$ 和 $b_k$ 之间有一条边。

数据范围

• $1 \leq N \leq 100000$；
• $1 \leq P \leq 100000$；
• 对于所有 $k \leq N-1$，$0 \leq a_k \leq N-1$ 且 $0 \leq b_k \leq N-1$；
• 输入中的边集描述的是一棵合法的树结构。

Output Format

输出一行，包含一个整数：获胜者最多能收集到的商品数。

5 5
0 1
0 2
2 3
2 4

4

Hint

样例解释

对于样例输入中的树结构，如下图所示，YAOGS 最优放置商品后，保证获胜者最多只能收集到 4 件商品。

下图展示了两种实现最优放置的方案。在第一种方案中，选择节点 $1$ 和 $3$ 可以收集到 4 件商品。在第二种方案中，选择节点 $0$ 和 $4$ 也可以收集到 4 件商品。

由 ChatGPT 4.1 翻译