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

P3554 [POI 2013] LUK-Triumphal arch

题目描述

给一颗 $n$ 个节点的树，初始时 $1$ 号节点被染黑，其余是白的。两个人轮流操作，一开始 B 在 $1$ 号节点。每一轮，A 选择 $k$ 个点染黑，然后 B 走到一个相邻节点，如果 B 当前处于白点则 B 胜，否则当 A 将所有点染为黑点时 A 胜。求能让 A 获胜的最小的 $k$。

输入格式

第一行读入一个整数 $n$，表示树的节点数

接下来 $n-1$ 行，每行读入两个用空格分隔的整数 $u,v$，表示 $u$、$v$ 之间有一条边。

输出格式

输出仅有一行，表示让 A 获胜的最小的 $k$。

输入输出样例 #1

输入 #1

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

输出 #1

3

说明/提示

$1\le n \le 3 \times 10^5$。

#5010. 「POI2013 R2」凯旋门 Triumphal arch

标签: 传统 | 时间限制: 5000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XX Olimpiada Informatyczna — II etap Łuk triumfalny

Bajtocja 的国王 Bajtazar 凯旋归国。Bajtocja 有 $n$ 座城市，仅由 $n-1$ 条道路连接，任意两城之间存在唯一路径（即道路网络构成一棵树）。

国王刚进入首都，编号为 $1$ 的城市，那里已建好一座凯旋门，供他胜利归来时通过。受到臣民热烈欢迎的 Bajtazar 决定举办一场盛大的巡游，计划从首都出发，游历所有城市。

除首都外，其他城市尚未准备迎接国王，未建凯旋门。Bajtazar 的顾问负责监督凯旋门建设，计划雇佣若干建筑队。每队每天可在一座任意城市建造一座凯旋门。遗憾的是，国王的巡游路线未知，仅知他每天从当前城市移动到相邻城市，且可能多次访问同一城市（但每城只需一座凯旋门）。

顾问需为每队支付相同费用，无论其建造多少凯旋门。他希望确保国王每到一城时，该城已有凯旋门，同时尽量减少雇佣的建筑队数量。请帮助他编写程序，计算所需的最少建筑队数量。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 300000)$，表示 Bajtocja 的城市数量。城市编号从 $1$ 到 $n$，首都为 $1$。

接下来的 $n-1$ 行，每行包含两个整数 $a, b$ $(1 \leq a, b \leq n)$，表示城市 $a$ 和 $b$ 间存在一条双向道路。

输出格式

输出一个整数，表示顾问所需雇佣的最少建筑队数量。

样例

输入

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

输出

3

在第一天，需在城市 $2, 3, 4$ 建造凯旋门。之后，在城市 $5, 6, 7$ 建造即可。

附加样例

1. $n=8191$，城市构成高度为 $12$ 的满二叉树。
2. $n=300000$，城市 $1, \ldots, n$ 沿单路径排列。
3. $n=5$，简单正确性样例。
4. $n=6$，简单正确性样例。
5. $n=10000$，九条长路径从根节点垂下。

数据范围与提示

对于 $50\%$ 的数据，$n \leq 10000$。