← 返回题目列表

Codeforces · 1375/G

G. 树修改

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

给你一棵有 $$$n$$$ 个顶点的树。您可以通过以下多步操作修改树的结构:

1. 选择三个顶点 $$$a$$$、$$$b$$$ 和 $$$c$$$,使得 $$$b$$$ 与 $$$a$$$ 和 $$$c$$$ 相邻。
2. 对于除 $$$b$$$ 之外与 $$$a$$$ 相邻的每个顶点 $$$d$$$,删除连接 $$$d$$$ 和 $$$a$$$ 的边,并添加连接 $$$d$$$ 和 $$$c$$$ 的边。
3. 删除连接 $$$a$$$ 和 $$$b$$$ 的边,并添加连接 $$$a$$$ 和 $$$c$$$ 的边。

作为示例,请考虑以下树:

下图说明了当我们对顶点 $$$2$$$、$$$4$$$ 和 $$$5$$$ 应用操作时发生的步骤顺序:

可以证明,每次操作后,得到的图仍然是一棵树。

找出将树转变为星形所需执行的最少操作数。星形树是一棵树,它有一个度数为 $$$n - 1$$$ 的顶点,称为中心,还有 $$$n - 1$$$ 度数为 $$$1$$$ 的顶点。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。

以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) 表示存在一条连接顶点 $$$u_i$$$ 的边和$$$v_i$$$。保证给定的边形成一棵树。

输出

打印一个整数——将树转变为星形所需的最少操作数。

可以证明,在给定的约束下,总是可以使用最多 $$$10^{18}$$$ 操作将树转换为星形。

示例

输入 #1

6
4 5
2 6
3 2
1 2
2 4

输出 #1

1

输入 #2

4
2 4
4 1
3 4

输出 #2

0

注意

第一个测试用例对应于语句中显示的树。正如我们之前所看到的,通过对顶点 $$$2$$$、$$$4$$$ 和 $$$5$$$ 应用单个操作,我们可以将树转换为以顶点 $$$5$$$ 为中心的星形树。

在第二个测试用例中,给定的树已经是一个中心位于顶点 $$$4$$$ 的星形树,因此无需执行任何操作。