AdditionalFile4850.zip

#4850. 「POI 2021/2022 R2」Agenci

标签: 传统 | 时间限制: 3000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXIX Olimpiada Informatyczna – II etap Agenci

在字节王国，有 $k$ 名特工需要执行一项任务：访问全国所有的 $n$ 座城市。为了不引起敌方反间谍部门的怀疑，他们必须遵守以下规则：

• 每天只有一名特工可以从当前所在城市移动到与之相邻的城市；
• 每座城市只能由一名特工访问（但同一位特工可以多次访问）。

字节王国的路网设计非常简约，仅由 $n-1$ 条道路构成，但从任意一座城市出发，总能通过某些路径到达其他任何城市。

请你编写一个程序，计算特工们访问所有城市所需的最短天数。假设特工们起始所在的城市已经算作被访问过。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$ $(2 \leq n \leq 500000, 1 \leq k \leq n)$，分别表示字节王国的城市数量和特工数量。城市编号从 $1$ 到 $n$。

第二行包含一个由 $k$ 个递增的整数组成的序列，范围在 $[1, n]$ 内，表示特工们的初始城市位置。

接下来的 $n-1$ 行描述字节王国的路网，每行包含一对整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示城市 $a$ 和 $b$ 之间有一条道路相连。

输出格式

你的程序应输出一行，包含一个整数，表示特工们访问所有城市所需的最短天数。

样例 1

输入

6 2
2 6
1 2
2 3
2 4
5 4
5 6

输出

5

第一名特工可以按顺序访问城市 $2 \rightarrow 1 \rightarrow 2 \rightarrow 3$，耗时 3 天；第二名特工可以访问 $6 \rightarrow 5 \rightarrow 4$，耗时 2 天。整个过程共需 5 天。

样例 2

见附加文件下 [age1.in](file:age1.in) 和 [age1.out](file:age1.out)。

该样例满足 $n=500000, a_{i}=i, b_{i}=i+1$，特工分别位于城市 $1$ 和 $n$，答案是 $499998$；

样例 3

见附加文件下 [age2.in](file:age2.in) 和 [age2.out](file:age2.out)。

该样例满足 $n=500000, a_{i}=1, b_{i}=i$，仅一名特工位于城市 $1$，答案是 $999997$。

数据范围与提示

详细子任务附加限制及分值如下表所示。