← 返回题目列表

Codeforces · 1774/E

E. 两个棋子

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

Cirno_9baka 有一个包含 $$$n$$$ 个节点的树。他愿意与你分享,这意味着你可以对其进行操作。

最初,树的节点$$$1$$$上有两个棋子。在一步中,您可以选择任何一块,并将其移动到相邻节点。您还将获得一个整数 $$$d$$$。您需要确保两块之间的距离不超过 $$$d$$$。

这两个部分中的每一个都有一系列节点,它们需要以任意顺序传递,最终它们必须返回到根。作为一个好奇的男孩,他想知道你需要采取的最少步骤。

输入

第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$2 \le d \le n \le 2\cdot 10^5$$$)。

以下 $$$n - 1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i, v_i$$$ $$$(1 \le u_i, v_i \le n)$$$,表示树的节点 $$$u_i, v_i$$$ 之间的边。

保证这些边形成一棵树。

下一行包含一个整数 $$$m_1$$$ ($$$1 \le m_1 \le n$$$) 和 $$$m_1$$$ 整数 $$$a_1, a_2, \ldots, a_{m_1}$$$ ($$$1 \le a_i \le n$$$, 所有 $$$a_i$$$ 都是不同的)  — 序列第一部分需要经过的节点。

第二行包含一个整数 $$$m_2$$$ ($$$1 \le m_2 \le n$$$) 和 $$$m_2$$$ 整数 $$$b_1, b_2, \ldots, b_{m_2}$$$ ($$$1 \le b_i \le n$$$, 所有 $$$b_i$$$ 都是不同的)  — 序列第二块需要经过的节点。

输出

输出一个整数——您需要采取的最少步骤。

示例

输入 #1

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

输出 #1

6

输入 #2

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

输出 #2

8

注意

在第一个示例中,这是长度为 $$$6$$$ 的一个可能的步骤序列。

- 第二个棋子按照路线 $$$1 \to 2 \to 4 \to 2 \to 1$$$ 移动。
- 然后,第一块沿着路线 $$$1 \to 3 \to 1$$$ 移动。

在第二个示例中,以下是长度为 $$$8$$$ 的一个可能的步骤序列:

- 第一个棋子沿着 $$$1 \to 2 \to 3$$$ 路线移动。
- 然后,第二块沿着路线 $$$1 \to 2$$$ 移动。
- 然后,第一块沿着路线 $$$3 \to 4 \to 3 \to 2 \to 1$$$ 移动。
- 然后,第二块沿着路线 $$$2 \to 1$$$ 移动。