310059: CF1776M. Parmigiana With Seafood
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Parmigiana With Seafood
题意翻译
给定一棵 $n$ 个节点的树 $(2 \leq n \leq 100000)$，第 $i$ 个节点上写着数字 $i$。 Alessandro 和 Bianca 轮流进行操作，每一次可以选择一个度数小于等于 $1$ 的节点取走，其中 Alessandro 先手。 Alessandro 想要使其取走的所有数字的最大值尽量大，而 Bianca 想要这个值尽量小。 在两者都取最优策略的情况下，输出这个值。 翻译by @南阳刘子骥题目描述
The "Parmigiana di melanzane" is a typical Italian dish. Alessandro and Bianca have very different tastes when it comes to it: Alessandro loves to eat Parmigiana with seafood, but Bianca thinks it is an atrocity! To decide which ingredients to include in the dish they prepare, they play the following game. There are $ n $ possible ingredients, labeled from $ 1 $ to $ n $ . The higher the label, the closer the ingredient is to being seafood. The ingredients are connected by $ n - 1 $ edges, in such a way as to form a tree. Alessandro and Bianca take turns, with Alessandro going first. They alternately choose a terminal ingredient $ x $ , that is an ingredient currently connected to at most one other ingredient, and remove it from the tree. If the terminal ingredient $ x $ was chosen by Alessandro, it goes in the recipe; if it was chosen by Bianca, it is discarded. The taste of the Parmigiana is measured as the maximum label of an ingredient in the recipe. Alessandro wants to maximize the taste, while Bianca wants to minimize the taste. If both play optimally, what is the taste of the Parmigiana?输入输出格式
输入格式
The first line contains an integer $ n $ ( $ 2\le n \le 100\,000 $ ) — the number of ingredients. Each of the following $ n-1 $ lines contain two integers $ u_i $ and $ v_i $ ( $ 1 \le u_i, v_i \le n $ , $ u_i \ne v_i $ ) — the ingredients that the $ i $ -th edge connects. It is guaranteed that the edges form a tree (i.e., any pair of ingredients is connected by the edges, possibly indirectly).
输出格式
Print the value of the taste if both Alessandro and Bianca play optimally.
输入输出样例
输入样例 #1
4
1 2
1 3
1 4输出样例 #1
4输入样例 #2
5
1 5
5 3
3 4
4 2输出样例 #2
3说明
In the first sample, Alessandro can choose terminal ingredient $ 4 $ in the first turn. This ingredient is added to the recipe. Since $ 4 $ is the maximum label of an ingredient, the taste is $ 4 $ regardless of the choices that follow. In the second sample, Bianca can make sure that neither ingredient $ 4 $ nor $ 5 $ are included in the recipe, in which case Alessandro can include $ 3 $ . Thus, the taste is $ 3 $ . Input
题意翻译
给定一棵 $n$ 个节点的树 $(2 \leq n \leq 100000)$，第 $i$ 个节点上写着数字 $i$。 Alessandro 和 Bianca 轮流进行操作，每一次可以选择一个度数小于等于 $1$ 的节点取走，其中 Alessandro 先手。 Alessandro 想要使其取走的所有数字的最大值尽量大，而 Bianca 想要这个值尽量小。 在两者都取最优策略的情况下，输出这个值。 翻译by @南阳刘子骥Output
**海鲜帕尔米贾纳**
**题意翻译**
给定一棵有 $ n $ 个节点的树 $(2 \leq n \leq 100000)$，第 $ i $ 个节点上写着数字 $ i $。Alessandro 和 Bianca 轮流进行操作，每一次可以选择一个度数小于等于 $ 1 $ 的节点取走，其中 Alessandro 先手。Alessandro 想要使其取走的所有数字的最大值尽量大，而 Bianca 想要这个值尽量小。在两者都取最优策略的情况下，输出这个值。
**题目描述**
"Parmigiana di melanzane"是一道典型的意大利菜。Alessandro 和 Bianca 对这道菜有着截然不同的口味：Alessandro 喜欢加上海鲜的帕尔米贾纳，但 Bianca 认为这是对这道菜的亵渎！为了决定在菜中加入哪些配料，他们玩以下游戏。
有 $ n $ 种可能的配料，从 $ 1 $ 到 $ n $ 标记。标签越高，配料越接近海鲜。配料通过 $ n - 1 $ 条边连接，形成一个树状结构。Alessandro 和 Bianca 轮流进行，Alessandro 先手。他们交替选择一个端点配料 $ x $，即一个当前最多只连接另一个配料的配料，并将其从树中移除。如果端点配料 $ x $ 被Alessandro选择，它就会进入食谱；如果它被Bianca选择，它就会被丢弃。
帕尔米贾纳的味道由食谱中配料标签的最大值来衡量。Alessandro想要最大化口味，而Bianca想要最小化口味。如果双方都采取最优策略，帕尔米贾纳的味道如何？
**输入输出格式**
**输入格式**
第一行包含一个整数 $ 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 $ 条边连接的配料。
保证边形成一个树（即，任意两种配料通过边连接，可能是间接的）。
**输出格式**
如果双方都采取最优策略，打印出味道的值。
**输入输出样例**
**输入样例 #1**
```
4
1 2
1 3
1 4
```
**输出样例 #1**
```
4
```
**输入样例 #2**
```
5
1 5
5 3
3 4
4 2
```
**输出样例 #2**
```
3
```
**说明**
在第一个样例中，Alessandro可以在第一轮选择端点配料 $ 4 $。这个配料被加入到食谱中。由于 $ 4 $ 是配料标签的最大值，所以无论后续的选择是什么，味道都是 $ 4 $。
在第二个样例中，Bianca可以确保配料 $ 4 $ 和 $ 5 $ 都不会被包含在食谱中，在这种情况下，Alessandro可以包含 $ 3 $。因此，味道是 $ 3 $。**海鲜帕尔米贾纳** **题意翻译** 给定一棵有 $ n $ 个节点的树 $(2 \leq n \leq 100000)$，第 $ i $ 个节点上写着数字 $ i $。Alessandro 和 Bianca 轮流进行操作，每一次可以选择一个度数小于等于 $ 1 $ 的节点取走，其中 Alessandro 先手。Alessandro 想要使其取走的所有数字的最大值尽量大，而 Bianca 想要这个值尽量小。在两者都取最优策略的情况下，输出这个值。 **题目描述** "Parmigiana di melanzane"是一道典型的意大利菜。Alessandro 和 Bianca 对这道菜有着截然不同的口味：Alessandro 喜欢加上海鲜的帕尔米贾纳，但 Bianca 认为这是对这道菜的亵渎！为了决定在菜中加入哪些配料，他们玩以下游戏。 有 $ n $ 种可能的配料，从 $ 1 $ 到 $ n $ 标记。标签越高，配料越接近海鲜。配料通过 $ n - 1 $ 条边连接，形成一个树状结构。Alessandro 和 Bianca 轮流进行，Alessandro 先手。他们交替选择一个端点配料 $ x $，即一个当前最多只连接另一个配料的配料，并将其从树中移除。如果端点配料 $ x $ 被Alessandro选择，它就会进入食谱；如果它被Bianca选择，它就会被丢弃。 帕尔米贾纳的味道由食谱中配料标签的最大值来衡量。Alessandro想要最大化口味，而Bianca想要最小化口味。如果双方都采取最优策略，帕尔米贾纳的味道如何？ **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $ 条边连接的配料。 保证边形成一个树（即，任意两种配料通过边连接，可能是间接的）。 **输出格式** 如果双方都采取最优策略，打印出味道的值。 **输入输出样例** **输入样例 #1** ``` 4 1 2 1 3 1 4 ``` **输出样例 #1** ``` 4 ``` **输入样例 #2** ``` 5 1 5 5 3 3 4 4 2 ``` **输出样例 #2** ``` 3 ``` **说明** 在第一个样例中，Alessandro可以在第一轮选择端点配料 $ 4 $。这个配料被加入到食谱中。由于 $ 4 $ 是配料标签的最大值，所以无论后续的选择是什么，味道都是 $ 4 $。 在第二个样例中，Bianca可以确保配料 $ 4 $ 和 $ 5 $ 都不会被包含在食谱中，在这种情况下，Alessandro可以包含 $ 3 $。因此，味道是 $ 3 $。
**题意翻译**
给定一棵有 $ n $ 个节点的树 $(2 \leq n \leq 100000)$，第 $ i $ 个节点上写着数字 $ i $。Alessandro 和 Bianca 轮流进行操作，每一次可以选择一个度数小于等于 $ 1 $ 的节点取走，其中 Alessandro 先手。Alessandro 想要使其取走的所有数字的最大值尽量大，而 Bianca 想要这个值尽量小。在两者都取最优策略的情况下，输出这个值。
**题目描述**
"Parmigiana di melanzane"是一道典型的意大利菜。Alessandro 和 Bianca 对这道菜有着截然不同的口味：Alessandro 喜欢加上海鲜的帕尔米贾纳，但 Bianca 认为这是对这道菜的亵渎！为了决定在菜中加入哪些配料，他们玩以下游戏。
有 $ n $ 种可能的配料，从 $ 1 $ 到 $ n $ 标记。标签越高，配料越接近海鲜。配料通过 $ n - 1 $ 条边连接，形成一个树状结构。Alessandro 和 Bianca 轮流进行，Alessandro 先手。他们交替选择一个端点配料 $ x $，即一个当前最多只连接另一个配料的配料，并将其从树中移除。如果端点配料 $ x $ 被Alessandro选择，它就会进入食谱；如果它被Bianca选择，它就会被丢弃。
帕尔米贾纳的味道由食谱中配料标签的最大值来衡量。Alessandro想要最大化口味，而Bianca想要最小化口味。如果双方都采取最优策略，帕尔米贾纳的味道如何？
**输入输出格式**
**输入格式**
第一行包含一个整数 $ 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 $ 条边连接的配料。
保证边形成一个树（即，任意两种配料通过边连接，可能是间接的）。
**输出格式**
如果双方都采取最优策略，打印出味道的值。
**输入输出样例**
**输入样例 #1**
```
4
1 2
1 3
1 4
```
**输出样例 #1**
```
4
```
**输入样例 #2**
```
5
1 5
5 3
3 4
4 2
```
**输出样例 #2**
```
3
```
**说明**
在第一个样例中，Alessandro可以在第一轮选择端点配料 $ 4 $。这个配料被加入到食谱中。由于 $ 4 $ 是配料标签的最大值，所以无论后续的选择是什么，味道都是 $ 4 $。
在第二个样例中，Bianca可以确保配料 $ 4 $ 和 $ 5 $ 都不会被包含在食谱中，在这种情况下，Alessandro可以包含 $ 3 $。因此，味道是 $ 3 $。**海鲜帕尔米贾纳** **题意翻译** 给定一棵有 $ n $ 个节点的树 $(2 \leq n \leq 100000)$，第 $ i $ 个节点上写着数字 $ i $。Alessandro 和 Bianca 轮流进行操作，每一次可以选择一个度数小于等于 $ 1 $ 的节点取走，其中 Alessandro 先手。Alessandro 想要使其取走的所有数字的最大值尽量大，而 Bianca 想要这个值尽量小。在两者都取最优策略的情况下，输出这个值。 **题目描述** "Parmigiana di melanzane"是一道典型的意大利菜。Alessandro 和 Bianca 对这道菜有着截然不同的口味：Alessandro 喜欢加上海鲜的帕尔米贾纳，但 Bianca 认为这是对这道菜的亵渎！为了决定在菜中加入哪些配料，他们玩以下游戏。 有 $ n $ 种可能的配料，从 $ 1 $ 到 $ n $ 标记。标签越高，配料越接近海鲜。配料通过 $ n - 1 $ 条边连接，形成一个树状结构。Alessandro 和 Bianca 轮流进行，Alessandro 先手。他们交替选择一个端点配料 $ x $，即一个当前最多只连接另一个配料的配料，并将其从树中移除。如果端点配料 $ x $ 被Alessandro选择，它就会进入食谱；如果它被Bianca选择，它就会被丢弃。 帕尔米贾纳的味道由食谱中配料标签的最大值来衡量。Alessandro想要最大化口味，而Bianca想要最小化口味。如果双方都采取最优策略，帕尔米贾纳的味道如何？ **输入输出格式** **输入格式** 第一行包含一个整数 $ 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 $ 条边连接的配料。 保证边形成一个树（即，任意两种配料通过边连接，可能是间接的）。 **输出格式** 如果双方都采取最优策略，打印出味道的值。 **输入输出样例** **输入样例 #1** ``` 4 1 2 1 3 1 4 ``` **输出样例 #1** ``` 4 ``` **输入样例 #2** ``` 5 1 5 5 3 3 4 4 2 ``` **输出样例 #2** ``` 3 ``` **说明** 在第一个样例中，Alessandro可以在第一轮选择端点配料 $ 4 $。这个配料被加入到食谱中。由于 $ 4 $ 是配料标签的最大值，所以无论后续的选择是什么，味道都是 $ 4 $。 在第二个样例中，Bianca可以确保配料 $ 4 $ 和 $ 5 $ 都不会被包含在食谱中，在这种情况下，Alessandro可以包含 $ 3 $。因此，味道是 $ 3 $。