[JSOI2013] 哈利波特与死亡圣器

题目描述

伏地魔的黑暗势力控制了魔法部与霍格沃茨魔法学校之后,哈利与罗恩、赫敏不得不逃亡在外,隐形遁迹。为了完成校长邓布利多的遗命,一直在暗中寻机销毁伏地魔魂器的哈利,意外地获悉如果他们能够拥有传说中的三件死亡圣器,伏地魔将必死无疑。 在凤凰社成员的帮助下,哈利一行人重新掌控了霍格沃茨。然而此举激怒了伏地魔,他很快率领大批食死徒和黑暗生物向霍格沃茨进军。麦格教授紧急疏散了霍格沃茨的学生,并开始了守卫霍格沃茨的战斗。 霍格沃茨魔法学校的主要建筑共有 $n$ 处,我们编号为 $1$ 到 $n$,这些建筑间由魔法道路连接,整体呈树状分布,即任意两个建筑间有且仅有一条路径相连(路径可以是一条或多条道路组成)。霍格沃茨历经多年风雨,每个建筑自身有许多保护魔法,比如“石墩触动咒”、“降敌陷阱咒”、“统统加护咒”等,只需有人前往施用咒语即能保卫建筑。 现在,伏地魔大军已经到达 $1$ 号建筑——学校大门,凤凰社成员也已经在大门迎战,并且已经启用了大门的保护魔法。然而伏地魔大军势力壮大,保护魔法只能延缓大军的进攻锋芒,他们仍能用一个小时攻克一个建筑,随后整个大军便随机前往与之相邻的另一个建筑(兵贵神速,大军移动过程不需要时间;兵法无常,他们有可能前往已经攻克的建筑)。 目前除了 $1$ 号建筑,其他建筑的保护魔法都尚未被启用,凤凰社决定派出一些成员去其他建筑施用咒语来启动保护魔法。每个凤凰社成员可以瞬间达到任意一个建筑,并用一个小时完成对该建筑保护魔法的启用,之后可以再前往其他的建筑。他们的任务是,保证不论伏地魔大军如何行动,大军所到建筑的保护魔法都已经启用。为了集中更多力量直接打击伏地魔大军,凤凰社希望派出施用咒语的成员数尽可能少。 请你计算,至少需要派出多少位成员。 注: - 伏地魔大军到达 $1$ 号建筑开始攻击的同时,凤凰社派出成员去其他建筑施咒。 - 当大军攻克某个建筑后,凤凰社成员可以在知道大军下一个小时去哪个建筑的情况下,再决定他们去哪些建筑施咒。这个过程也不需要时间。 - 已经启用过保护魔法的建筑无需再施咒,即便大军攻克该建筑以后某个时候又回到这个建筑,大军也会在这个建筑持续攻击一个小时后再离开。

输入输出格式

输入格式


第一行一个整数 $n$,表示建筑的数量。 接下来 $n-1$ 行,每行两个整数 $u,v$,表示建筑 $u$ 和建筑 $v$ 之间有一条魔法道路。

输出格式


一行一个整数,表示最少需要派出施用咒语的成员数。

输入输出样例

输入样例 #1

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

输出样例 #1

3

说明

### 数据范围 对于 $100\%$ 的数据,$1\leq n\leq 3\times 10^5$。