AT_pakencamp_2023_day2_b Salesman X

パソコン力を高めるの国有 $N$ 个城市，这些城市通过 $N-1$ 条双向道路连接。第 $i$ 条道路连接城市 $A_i$ 和 $B_i$。除了道路之外无法在城市间移动，并且从任一城市到另一城市都可以通过若干道路到达。换言之，该国的城市和道路构成了一棵树。 巡回推销员 Mr.X 需要前往各城市开展销售活动。整个销售需要两天完成。他最初在城市 $1$，第一天需要访问城市 $X_1, X_2, \cdots, X_M$。然后在某个城市住宿一晚，第二天需要访问城市 $Y_1, Y_2, \cdots, Y_M$，最后必须到达城市 $S$ 结束销售。每一天访问的城市顺序不作要求。此外，每天开始所在的城市视为已经访问过。 Mr.X 希望完成销售所经过的道路次数尽量少。请你求出在 $2$ 天内经过道路次数的最小值。

输入通过标准输入按如下格式给出。 > $N$ $M$ $S$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_{N-1}$ $B_{N-1}$ > $X_1$ $X_2$ ... $X_M$ > $Y_1$ $Y_2$ ... $Y_M$

请输出一个整数，表示所需通过道路的最小次数。

## 配分 对于以下小任务有不同的分值。 1. （$200$ 分）$N \leq 1000$ 2. （$300$ 分）无额外约束。 ## 样例解释 1 例如，第一天依次访问城市 $1, 2, 1, 3$，第二天依次访问城市 $3, 1, 2, 1, 4$，合计经过 $7$ 次道路。这是最优方式之一。 # 数据范围 - $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$ - 输入中所有数均为整数。 由 ChatGPT 5 翻译