← 返回题目列表

AtCoder · pakencamp_2023_day2_b

B. 推销员 X

中文机器翻译题面 查看原题

配点 : 500 点

問題文

提高计算机技能的国家 N 城市并将它们连接起来 N - 1 由双向道路组成。i 真正的道路是城市 连接 A_i, B_i 。您不能使用道路以外的任何方式在城市之间旅行,并且您可以通过多条道路从任何国家前往任何其他国家。换句话说,这个国家形成了一个树形结构作为图。

X 先生是一名旅行推销员,他在城市之间进行销售旅行。销售将持续两天。他是第一座城市 1 进城第一天。 访问 X_1, X_2, \cdots ,X_M 。之后入住城市,第二天返回城市。 参观 Y_1, Y_2, \cdots ,Y_M ,最后参观这座城市 您需要到达 S 并完成销售。在这里,每天访问的城市的顺序并不重要。此外,您在某一天开始时所在的城市也被视为在该天访问过。

Mr.X 希望尽可能少地完成他的销售旅程。2 求您一天内经过该路的最少次数。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq N
  • 1 \leq S \leq N
  • 1 \leq A_i, B_i \leq N \ (1 \leq i \leq N - 1)
  • 给定的图是一棵树。
  • 1 \leq X_i, Y_i \leq N
  • 所有输入均为整数。

配点

分数由以下子作业决定。

  1. (200 点) N \leq 1000
  2. (300 点)没有额外的限制。

入力

输入将以以下形式通过标准输入给出。

N M S
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
X_1 X_2 \cdots X_M
Y_1 Y_2 \cdots Y_M

出力

请将答案输出在一行内。


入力例 1

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

出力例 1

7

例如,第一天,城市 1, 2, 1, 3 ,第二天就是进城了。 如果按顺序访问 3, 1, 2, 1, 4 ,总数将为 7 穿过环路。这是最好的方法之一。 请针对


入力例 2

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

出力例 2

20