#lCAlydlt60x6308. 疫情控制

疫情控制

好的,这是整理好的题面,不含解题思路,只包含样例解释。


题目描述

H 国有 nn 个城市,这些城市通过 n1n-1 条双向道路连通成一棵树,1 号城市是首都(根节点)
首都爆发了高危传染病,当局要控制疫情,不让疫情扩散到边境城市(即叶子节点所表示的城市)。
决定动用军队在一些城市建立检查点,使得从首都到每个边境城市的每一条路径上都至少有一个检查点,边境城市自身也可以建立检查点。
注意:首都不允许建立检查点。

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

不同的军队可以同时移动。

问:最少需要多少小时才能控制疫情(即完成上述检查点布置)?
如果无法控制疫情,输出 1-1


输入格式

第一行一个整数 nn,表示城市个数。
接下来 n1n-1 行,每行三个整数 u,v,wu,v,w,表示城市 uu 到城市 vv 有一条长度为 ww 的双向道路。数据保证是一棵树,且根节点是 1。
接下来一行一个整数 mm,表示军队个数。
接下来一行 mm 个整数,表示这 mm 支军队分别驻扎的城市编号。

输出格式

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

数据范围

  • 2mn500002 \le m \le n \le 50000
  • 0<w<1090 < w < 10^9

输入样例

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

输出样例

3

样例解释

树的结构

城市 4 个,边:

  1. 1—2 长度 1
  2. 1—3 长度 2
  3. 3—4 长度 3

树形:

    1
   / \
  2   3
      |
      4

其中叶子节点是 2 和 4(边境城市)。

军队情况

m=2m=2,两支军队都在城市 2 驻扎。

目标

从首都 1 到边境城市 2 和 4 的每条路径上都要有检查点,且首都不设检查点。


方案

边境城市 2 的路径只有 1-2,需要在 2 或者这条路径上别的非首都城市设检查点。
边境城市 4 的路径是 1-3-4,需要在 3 或 4 设检查点。

当前军队都在 2。
至少需要一个军队移动到 3(或 4)去设检查点,因为 2 已经在边境 2 路径上了,但 4 的路径上没有军队。

从 2 出发,到 3 的最短路径:2-1-3,长度 1+2=3 小时。
另一支军队留在 2 设检查点。

移动一支军队到 3 需要 3 小时(同时另一支军队已经在 2),之后:

  • 2 有检查点,覆盖路径 1-2。
  • 3 有检查点(或可以再走一步到 4 设检查点,但 3 已经能覆盖 1-3-4,因为 3 在路径上),实际上在 3 设点就能覆盖到叶子 4 吗?
    路径 1-3-4,如果只在 3 设点,则到达 4 的路径经过 3 已有检查点,所以可行。

因此最小时间是 3 小时。


输出 3