← 返回比赛

已结束 GESP巅峰赛#29

← 上一题下一题 →

A7093 | $夜巡城的望炬布防$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

雾港城的夜巡军要在城内 $n$ 个路口架设“望炬”。城里的路网恰好是一棵树（无向、连通、无环），第 $i$ 条古道连接路口 $u_i$ 与 $v_i$。在某个路口点燃一盏望笮信，它会 同时照亮该路口及其所有直接相邻的路口 。请你安排点灯位置，使 全城所有路口都被照亮 ，并将所需望笮信的最少数量汇报给统领。

输入格式

- 第一行一个整数 $n$； - 接下来 $n-1$ 行，每行两个整数 $u,v$，表示一条连接 $u$ 与 $v$ 的无向古道

输出格式

- 输出一个整数，表示最少需要点燃的望笮信数量。

输入输出样例

输入 #1

3
1 2
2 3

输出 #1

输入 #2

输出 #2

- $1\le n\le 2\times 10^5$ - $1\le u,v\le n$ 测试点分层（仅按 $n$ 的范围，共 25 组数据（T01～T25）） 层级$n$ 范围A$1 \le n \le 20$B$20 < n \le 500$C$500 < n \le 2\times 10^5$

C++ 编辑器

输入

输出