HBC16565[NOIP2012]疫情控制题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

H国有n个城市，这n个城市用n-1条双向道路相互连通构成一棵树，1号城市是首都，也是树中的根节点， H 国的首都爆发了一种危害性极高的传染病，当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点，但特别要注意的是，首都是不能建立检查点的，

    H 国有n 个城市，这 n 个城市用n-1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。     H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。     现在，在H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。     请问最少需要多少个小时才能控制疫情。注意：不同的军队可以同时移动。

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC16565[NOIP2012]疫情控制题解