← 返回题目列表

AtCoder · summerfes2018_d

D. 树--->路径

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

配点 : 150 点

問題文

鸭嘴兽君是打靶奖品。 N 我收到了一棵由顶点组成的连接的无向树。 如果直接搬运的话会很困难,所以我想用树作为路径。 (路径是一棵树,其中所有顶点的度数最多为 2。) platypus 使用以下操作使树成为路径。

  1. 添加任意数量的顶点
  2. 在树顶点和步骤 1 中添加的顶点之间添加任意数量的无向边。 (不能将树的顶点或步骤 1 中添加的顶点与边连接起来。)
  3. 从步骤 2 中创建的图形中,删除任意数量的边,直到没有循环,使其成为一条连通路径。

通过上述操作,鸭嘴兽想要最小化步骤 1 中添加的顶点数量。 编写一个程序,使用上述操作找到使给定树成为路径的最小附加顶点数。

制約

所有测试用例都满足以下约束。

  • 2 \leq N \leq 200000
  • 1 \leq u_{i},v_{i} \leq N (1 \leq i \leq N-1)
  • 给定的图是一棵树。 写入

入力

输入是按以下格式从标准输入给出的。

N
u_{1} v_{1}
u_{2} v_{2}
:
u_{N-1} v_{N-1}
  • 第一行是一个整数 N 。这表示鸭嘴兽获得的图的顶点数。
  • 继续 N-1 行数过多 i 行有两个整数 u_{i} 和 在 v_{i} 用空格分隔。这是图表 这表明 i 第一条边是顶点 u_{i} 和 在v_{i} 已连接。

出力

输出最少数量的附加顶点,使给定图成为一条到标准输出的一行路径。 只需添加


入力例 1

7
1 2
3 7
4 2
1 3
5 2
3 6

出力例 1

2

2 顶点即可。 添加顶点 如果你称其为 X ,Y , X 和 在 4 , X 和 在 5 , Y 和 在 5 , Y 和 在 6 与边连接起来,最后 如果我们擦除连接 2 和 在 5 , 3 和 在 6 的每条边,我们得到 名为 6 - Y - 5 - X - 4 - 2 - 1 - 3 - 7的连续路径仍然存在。 1 由于这个图不能仅仅通过添加一个顶点就变成一条路径,所以答案是 2 。


入力例 2

5
1 3
3 2
2 5
5 4

出力例 2

0

由于给定的图已经是一条路径,所以答案是 0 。


入力例 3

9
3 5
4 6
4 2
5 9
8 5
1 2
7 4
3 1

出力例 3

2