分数: 900 点
问题陈述
我们有一棵树 N 顶点。 顶点已编号 0 通过 N - 1,以及 i第边缘 (0 ≤ i < N - 1) 连接顶点 a_i 和 b_i。 对于每对顶点 u 和 v (0 ≤ u, v < N),我们定义距离 d(u, v) 作为路径中的边数 u-v.
预计其中一个顶点将被来自外太空的外星人入侵。 Snuke 希望在入侵发生时立即识别该顶点。 为此,他决定在一些顶点安装天线。
首先,他决定天线的数量, K (1 ≤ K ≤ N)。 然后,他选择 K 不同的顶点, x_0, x_1, ..., x_{K - 1},他在其上安装天线 分别为 0, 1, ..., K - 1。 如果顶点 v 被外星人入侵,天线 k (0 ≤ k < K) 将输出距离 d(x_k, v)。 基于这些 K 输出,Snuke将识别被入侵的顶点。 因此,为了识别被入侵的顶点,无论入侵哪一个顶点,都必须满足以下条件:
- 对于每个顶点 u (0 ≤ u < N),考虑向量 (d(x_0, u), ..., d(x_{K - 1}, u))。这些 N 向量是不同的。
找到最小值 K,满足条件时的天线数量。
约束
- 2 ≤ N ≤ 10^5
- 0 ≤ a_i, b_i < N
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_0 b_0
a_1 b_1
:
a_{N - 2} b_{N - 2}
输出
打印最小值 K,满足条件时的天线数量。
示例输入 1
5 0 1 0 2 0 3 3 4
示例输出 1
2
例如,在 Vertex 上安装天线 1 和 3。 那么,以下五个向量是不同的:
- (d(1, 0), d(3, 0)) = (1, 1)
- (d(1, 1), d(3, 1)) = (0, 2)
- (d(1, 2), d(3, 2)) = (2, 2)
- (d(1, 3), d(3, 3)) = (2, 0)
- (d(1, 4), d(3, 4)) = (3, 1)
示例输入 2
2 0 1
示例输出 2
1
例如,在 Vertex 上安装天线 0.
示例输入 3
10 2 8 6 0 4 1 7 6 2 3 8 6 6 9 2 4 5 8
示例输出 3
3
例如,在 Vertex 上安装天线 0, 4, 9.