P1084 [NOIP 2012 提高组] 疫情控制

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

无

无

【输入输出样例说明】 第一支军队在 $2$ 号点设立检查点，第二支军队从 $2$ 号点移动到$ 3$ 号点设立检查点，所需时间为 $3$ 个小时。 【数据范围】 保证军队不会驻扎在首都。 - 对于 $20\%$ 的数据，$2 \le n\le 10$； - 对于 $40\%$ 的数据，$2 \le n\le 50$，$0