E. Two Chess Pieces
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.
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 a single integer — the minimum steps you need to take.
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\).