#2607. 「NOIP2012」疫情控制

内存限制:128 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Planet6174

题目描述

H 国有 nnn 个城市,这 nnn 个城市用 n−1n - 1n1 条双向道路相互连通构成一棵树,111 号城市是首都,也是树中的根节点。

H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意的是,首都是不能建立检查点的。

现在,在 H 国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度(单位:小时)。

请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。

输入格式

第一行一个整数 nnn,表示城市个数。

接下来的 n−1n-1n1 行,每行 333 个整数,uuuvvvwww,每两个整数之间用一个空格隔开,表示从城市 uuu 到城市 vvv 有一条长为 www 的道路。数据保证输入的是一棵树,且根节点编号为 111

接下来一行一个整数 mmm,表示军队个数。

接下来一行 mmm 个整数,每两个整数之间用一个空格隔开,分别表示这 mmm 个军队所驻扎的城市的编号。

输出格式

共一行,包含一个整数,表示控制疫情所需要的最少时间。如果无法控制疫情则输出 −1-11

样例

样例输入

4
1 2 1
1 3 2
3 4 3
2
2
2

样例输出

3

样例说明

第一支军队在 222 号点设立检查点,第二支军队从 222 号点移动到 333 号点设立检查点,所需时间为 333 个小时。

数据范围与提示

保证军队不会驻扎在首都。

对于10%10\%10% 的数据,有 n≤10n \leq 10n10

对于20%20\%20% 的数据,有 n≤50n \leq 50n50w<105w < 10^5w<105

对于30%30\%30% 的数据,有 n≤1,000n \leq 1,000n1,000w<106w < 10^6w<106

对于40%40\%40% 的数据,有 n≤10,000n \leq 10,000n10,000

对于50%50\%50% 的数据,有 n≤50,000n \leq 50,000n50,000

对于80%80\%80% 的数据,有 n≤100,000n \leq 100,000n100,000

对于100%100\%100% 的数据,有 2≤m≤n≤300,0002 \leq m \leq n \leq 300,0002mn300,000 0<w<1090 < w < 10^90<w<109