← 返回题目列表

Codeforces · 1029/E

E. 小距离树

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

给你一个由 $$$n$$$ 个顶点组成的无向树。无向树是具有 $$$n - 1$$$ 边的连通无向图。

您的任务是添加最少数量的边,使得从顶点 $$$1$$$ 到任何其他顶点的最短路径长度最多为 $$$2$$$。请注意,不允许添加循环和多条边。

输入

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

以下 $$$n - 1$$$ 行包含边:边 $$$i$$$ 作为一对顶点 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) 给出。保证给定的边形成一棵树。保证给定的边中不存在环路和重边。

输出

打印一个整数 - 为了使从顶点 $$$1$$$ 到任何其他顶点的最短距离最多为 $$$2$$$,必须添加的最小边数。请注意,不允许添加循环和多条边。

示例

输入 #1

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

输出 #1

2

输入 #2

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

输出 #2

0

输入 #3

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

输出 #3

1

注意

第一个示例对应的树:答案是 $$$2$$$,一些可能的答案如下:$$$[(1, 5), (1, 6)]$$$, $$$[(1, 4), (1, 7)]$$$, $$$[(1, 6), (1, 7)]$$$。

第二个例子对应的树:答案是$$$0$$$。

第三个例子对应的树:答案是$$$1$$$,只有一种可能的方法是添加边$$$(1, 3)$$$。