AT_apc001_e.Antennas on Tree

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一棵包含 $N$ 个顶点的树。顶点编号为 $0$ 到 $N-1$ 。对于每一条边 $i$ （ $0 \leq i < N-1$ ），它连接着顶点 $a_i$ 和 $b_i$ 。对于每一对顶点 $u, v$ （ $0 \leq u, v < N$ ），我们将距离 $d(u, v)$ 定义为 $u$ 到 $v$ 的路径上经过的边的数量。

在不久的将来，预计会有宇宙人袭击其中一个顶点。SunuKe 君希望，在宇宙人袭击时能够立即确定被袭击的顶点。为此，他打算提前在树上的若干顶点安装天线。

首先，可以自由选择天线的个数 $K$ （ $1 \leq K \leq N$ ）。然后可以自由选择 $K$ 个各不相同的顶点 $x_0, x_1, ..., x_{K-1}$ ，并分别在每个顶点上安装天线 $0, 1, ..., K-1$ 。当某顶点 $v$ 被宇宙人袭击时，第 $k$ 个天线（ $0 \leq k < K$ ）会输出 $d(x_k, v)$ 。SunuKe 君通过这 $K$ 个输出值，试图唯一确定被袭击的顶点。因此，为使无论哪个顶点被宇宙人袭击时都能唯一确定该顶点，需满足以下条件：

对于每个顶点 $u$ （ $0 \leq u < N$ ），设向量为 $(d(x_0, u), ..., d(x_{K-1}, u))$ ，则这 $N$ 个向量必须完全不同。

请你求出，满足条件时，所需天线的最小个数 $K$ 。

输入格式

输入以如下格式从标准输入读入：

$N$ $a_0$ $b_0$ $a_1$ $b_1$ $\dots$ $a_{N-2}$ $b_{N-2}$

输出格式

输出满足条件所需的最少天线数量 $K$ 。

输入输出样例

输入#1
```
5
0 1
0 2
0 3
3 4
```
输出#1
```
2
```
输入#2
```
2
0 1
```
输出#2
```
1
```
输入#3
```
10
2 8
6 0
4 1
7 6
2 3
8 6
6 9
2 4
5 8
```
输出#3
```
3
```

说明/提示

限制条件

$2 \leq N \leq 10^5$
$0 \leq a_i, b_i < N$
给定的图保证是一棵树。

样例说明 1

例如，可以在顶点 $1$ 、 $3$ 安装天线。此时，以下 $5$ 个向量均不相同：

$(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

例如，可以只在顶点 $0$ 安装一个天线。

样例说明 3

例如，可以在顶点 $0$ 、 $4$ 、 $9$ 安装天线。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页