Two Chess Pieces
Contest: Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1900
Tags: dfs and similar, dp, greedy, trees

Cirno_9baka has a tree with $$$n$$$ nodes. He is willing to share it with you, which means you can operate on it.

Initially, there are two chess pieces on the node $$$1$$$ of the tree. In one step, you can choose any piece, and move it to the neighboring node. You are also given an integer $$$d$$$. You need to ensure that the distance between the two pieces doesn't ever exceed $$$d$$$.

Each of these two pieces has a sequence of nodes which they need to pass in any order, and eventually, they have to return to the root. As a curious boy, he wants to know the minimum steps you need to take.

Input format:
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$2 \le d \le n \le 2\cdot 10^5$$$).

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i, v_i$$$ $$$(1 \le u_i, v_i \le n)$$$, denoting the edge between the nodes $$$u_i, v_i$$$ of the tree.

It's guaranteed that these edges form a tree.

The next line contains an integer $$$m_1$$$ ($$$1 \le m_1 \le n$$$) and $$$m_1$$$ integers $$$a_1, a_2, \ldots, a_{m_1}$$$ ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are distinct)  — the sequence of nodes that the first piece needs to pass.

The second line contains an integer $$$m_2$$$ ($$$1 \le m_2 \le n$$$) and $$$m_2$$$ integers $$$b_1, b_2, \ldots, b_{m_2}$$$ ($$$1 \le b_i \le n$$$, all $$$b_i$$$ are distinct)  — the sequence of nodes that the second piece needs to pass.

Output format:
Output a single integer  — the minimum steps you need to take.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, here is one possible sequence of steps of length $$$6$$$.

- The second piece moves by the route $$$1 \to 2 \to 4 \to 2 \to 1$$$.
- Then, the first piece moves by the route $$$1 \to 3 \to 1$$$.

In the second sample, here is one possible sequence of steps of length $$$8$$$:

- The first piece moves by the route $$$1 \to 2 \to 3$$$.
- Then, the second piece moves by the route $$$1 \to 2$$$.
- Then, the first piece moves by the route $$$3 \to 4 \to 3 \to 2 \to 1$$$.
- Then, the second piece moves by the route $$$2 \to 1$$$.

Example input:
4 2
1 2
1 3
2 4
1 3
1 4

Example output:
6

Example input:
4 2
1 2
2 3
3 4
4 1 2 3 4
1 1

Example output:
8

Editorial:
We can find that for any $$$d$$$-th ancestor of some $$$b_i$$$, the first piece must pass it some time. Otherwise, we will violate the distance limit. The second piece must pass the $$$d$$$-th ancestor of each $$$b_i$$$ as well. Then we can add the $$$d$$$-th ancestor of each $$$a_i$$$ to the array $$$b$$$, and add the $$$d$$$-th ancestor of each $$$b_i$$$ to the array $$$a$$$.
Then we can find now we can find a solution that each piece only needs to visit its nodes using the shortest route, without considering the limit of $$$d$$$, and the total length can be easily computed. We can find that if we adopt the strategy that we visit these nodes according to their DFS order(we merge the array of $$$a$$$ and $$$b$$$, and sort them according to the DFS order, if the first one is from $$$a$$$, we try to move the first piece to this position, otherwise use the second piece), and move the other piece one step closer to the present piece only if the next step of the present piece will violate the distance limit, then we can ensure the movement exactly just let each piece visit its necessary node without extra operations.