嚣哥是全国唯一巧克力金币供应商。全国共有 $ n $ 个城市,他在其中 $ m $ 个设立了巧克力金币工厂。 现在 $ k $ 个城市准备举办巧克力金币节,急需巧克力金币,嚣哥要尽快以货车运送巧克力金币到这些城市。 为了方便叙述,我们对全国所有城市从 $ 1∼n $ 编号,嚣哥工厂的所在城市为 $ f_1, f_2, \cdots, f_m $, 需要把巧克力金币送到的城市为 $ d_1, d_2, \cdots, d_k $。
全国共有 $ n - 1 $ 条公路,分别连接一对城市。 货车可以在一小时从公路连接的一个城市驶到另一个城市。保证任意两个城市透过若干条公路相连。
嚣哥的每个工厂都有足够(多于 $ n $ 辆)的货车,货车可以在不同工厂同时出发,各自把巧克力金币送往目的地。 如果某个工厂的所在城市恰好举办巧克力金币节,则不需任何时间把巧克力金币送达。 请你帮嚣哥计算,至少需要多少个小时把巧克力金币送达举行巧克力金币节的城市?
输入格式
第一行三个整数 $ n, m, k $。
第二行 $ m $ 个整数表示 $ f_i $。保证 $ i \neq j $ 则 $ f_i \neq f_j $。
第三行 $ k $ 个整数表示 $ d_i $。保证 $ i \neq j $ 则 $ d_i \neq d_j $。
接下来 $ n - 1 $ 行,每行两个整数 $ u $ 和 $ v $,表示有一条公路连接编号为 $ u $ 和 $ v $ 的城市。保证 $ u \neq v $。
输出格式
仅一行一个整数表示答案,以小时作单位。
数据范围
对于 $ 60\% $ 的数据:$ m, k \le n \le 500 $
对于 $ 100\% $ 的数据:$
1 \le m, k \le n \le 5 \times 10^4; \;
1 \le f_i, d_i, u, v \le n $
Sample Test Cases
Input | Output | |
---|---|---|
5 2 2 1 2 3 4 1 4 2 5 4 5 3 5 |
2 |
Scoring: Per Case
Authored by s16f22
Appeared in 2021 SDIC 练习