配点 : 150 点
問題文
鸭嘴兽君是打靶奖品。 N 我收到了一棵由顶点组成的连接的无向树。 如果直接搬运的话会很困难,所以我想用树作为路径。 (路径是一棵树,其中所有顶点的度数最多为 2。) platypus 使用以下操作使树成为路径。
- 添加任意数量的顶点
- 在树顶点和步骤 1 中添加的顶点之间添加任意数量的无向边。 (不能将树的顶点或步骤 1 中添加的顶点与边连接起来。)
- 从步骤 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