← 返回题目列表

AtCoder · apc001_e

E. 树上的天线

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

分数: 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.