F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5174. -- [Jsoi2013]哈利波特与死亡圣器

5174: [Jsoi2013]哈利波特与死亡圣器

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 49  Solved: 26
[Submit][Status][Discuss]

Description

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

Input

第一行,包含1个整数,n,表示建筑的数量。
接下来n-1行,每行两个整数u、v(1≤u,v≤n,u≠v),表示建筑u和建筑v之间有一条魔法道路。
数据保证任意两个建筑连通。
1≤n≤300000。

Output

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

Sample Input

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

Sample Output

3

HINT

Source

[Submit][Status][Discuss]

HOME Back