[AdditionalFile4905.zip](file://AdditionalFile4905.zip?type=additional_file)

P5969 [POI 2016] Nadajniki

题目描述

比特镇一共有 $n$ 个房子，编号依次为 $1$ 到 $n$，这些房子通过 $n-1$ 条无向道路连通在一起，形成了一棵树的结构。

Bytesear 要在比特镇实施 Wifi 搭建计划，他要让 Wifi 覆盖到比特镇的每一条道路。

Bytesear 可以安置无限多个 Wifi 发射器，但是只能安置在树上的节点上，一个房子可以安置多个 Wifi 发射器。

对于一条道路 $(a,b)$，如果它满足以下两个条件之中的至少一个，那么这条边将被 Wifi 覆盖：

• $a$ 点放置了 Wifi 发射器或者 $b$ 点放置了 Wifi 发射器。
• 与 $a$ 点或 $b$ 点直接相邻的点中，至少放置了两个 Wifi 发射器。

请帮助 Bytesear 规划一个最优的放置方案，使得 Wifi 覆盖到比特镇的每一条道路，且放置的 Wifi 发射器总数尽可能少。

输入格式

第一行包含一个正整数 $n$，表示房子的总数。

接下来 $n-1$ 行，每行两个正整数 $a,b$，表示 $a$ 点和 $b$ 点之间有一条边。

输出格式

输出一行一个整数，即最少的 Wifi 发射器总数。

输入输出样例 #1

输入 #1

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

输出 #1

2

说明/提示

对于 $100\%$ 的数据，$2\le n\le2 \times 10^5$，$1\le a,b\le n$。

---

样例解释：

在 $3$ 号点放置两个 Wifi 发射器。

#4905. 「POI2016 R1」发射器 Transmitters

标签: 传统 | 时间限制: 8000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Nadajniki

Bajtazar 成为字节镇下古老盐矿的新任主管。为了吸引更多游客，他决定在矿洞通道里安装无线网络。

盐矿有 $n$ 个腔室，通过 $n-1$ 条通道相连，任何两个腔室都能通过通道到达。Bajtazar 计划在腔室中放置 Wi-Fi 发射器，确保每条通道都有网络覆盖。要让连接腔室 $a$ 和 $b$ 的通道有网络，需满足以下至少一个条件：

• 腔室 $a$ 或 $b$ 中有发射器；
• 从腔室 $a$ 或 $b$ 出发，最多经过一条通道可达的腔室集合中，至少有两个发射器。

Bajtazar 想知道，至少需要放置多少发射器才能覆盖所有通道。每间腔室可放置任意多个发射器。

输入格式

输入第一行是一个正整数 $n$，表示盐矿的腔室数量，腔室编号从 $1$ 到 $n$。

接下来的 $n-1$ 行描述通道，每行两个整数 $a$ 和 $b$ $(1 \leq a, b \leq n, a \neq b)$，表示 $a$ 号和 $b$ 号腔室间有一条通道。

输出格式

输出一行一个整数，表示 Bajtazar 所需的最少发射器数量。

样例 1

输入

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

输出

2

第一个样例中，在 $2$ 号和 $6$ 号腔室各放一个发射器即可；第二个样例中，在 $3$ 号腔室放两个发射器即可。

样例 2

输入

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

输出

2

附加样例

1. $n=16$，腔室 $i$ 与 $\lfloor i / 2 \rfloor$ $(2 \leq i \leq n)$ 相连；
2. $n=303$，$2$ 号腔室连 $1$ 号和 $3$ 号，$1$、$2$、$3$ 号各连 $100$ 个其他腔室，最优解在 $2$ 号腔室放两个发射器；
3. $n=200000$，腔室 $i$ 与 $i+1$ $(1 \leq i \leq n-1)$ 相连。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 10$	$15$
$2$	$n \leq 500$	$20$
$3$	$n \leq 200000$，每个腔室至多连三条通道	$25$
$4$	$n \leq 200000$	$40$