CF1776M Parmigiana With Seafood

“Parmigiana di melanzane” 是一道典型的意大利菜。Alessandro 和 Bianca 对这道菜的口味截然不同：Alessandro 喜欢加海鲜，而 Bianca 认为这简直是暴行！为了决定菜品中包含哪些配料，他们玩了如下的游戏。 共有 $n$ 种可能的配料，编号从 $1$ 到 $n$。编号越大，配料越接近海鲜。这些配料通过 $n-1$ 条边连接，形成一棵树。Alessandro 和 Bianca 轮流行动，Alessandro 先手。他们轮流选择一个“末端配料” $x$，即当前至多与一个其他配料相连的配料，并将其从树中移除。如果 $x$ 是 Alessandro 选的，则该配料会被加入菜谱；如果是 Bianca 选的，则该配料会被丢弃。 Parmigiana 的“口味”定义为菜谱中配料编号的最大值。Alessandro 希望最大化口味，而 Bianca 希望最小化口味。如果双方都采取最优策略，Parmigiana 的口味是多少？

第一行包含一个整数 $n$（$2\le n \le 100\,000$），表示配料的数量。 接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第 $i$ 条边连接的两个配料。 保证这些边构成一棵树（即任意两种配料之间都可以通过这些边间接或直接连通）。

输出一个整数，表示在双方都采取最优策略的情况下，Parmigiana 的口味值。

在第一个样例中，Alessandro 可以在第一回合选择末端配料 $4$。该配料会被加入菜谱。由于 $4$ 是配料中的最大编号，无论后续如何选择，口味值都是 $4$。  在第二个样例中，Bianca 可以确保 $4$ 和 $5$ 都不会被加入菜谱，这样 Alessandro 只能加入 $3$。因此，口味值为 $3$。  由 ChatGPT 4.1 翻译