HBC20031[HNOI2003]消防局的设立题解

冷默言语算法基础篇 2023-11-20 22:29:02 51 0

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地，起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构，如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d，由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局，消防局只能修建在基地里，每个消防局有能力扑灭与它距

2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力扑灭与它距离不超过2的基地的火灾。你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时，消防队有能力及时扑灭火灾。