Vlad and Unfinished Business

题意翻译

### 题意简述 有一棵 $n$ 个节点的树，从节点 $x$ 出发，需要到 $a_1,a_2\dots a_k$ 节点完成任务（任意顺序），最终到达终点 $y$。走每条边的花费为 $1$，求最小花费。 ### 输入格式 第一行一个正整数 $t$ 表示数据组数。 对于每组数据，第一行两个正整数 $n,k$ 表示节点数量和任务数量；第二行两个正整数 $x,y$ 表示起点编号和终点编号；第三行 $k$ 个正整数 $a_1,a_2\dots a_k$ 表示任务所在节点编号；接下来 $n-1$ 行，每行两个正整数表示一条边的两个端点编号。 ### 输出格式 对于每组数据，输出一行一个正整数表示最小花费。 ### 数据规模 $t\le 10^4,1\le n,k\le 2\times 10^5,\sum n\le2\times10^5$

题目描述

Vlad and Nastya live in a city consisting of $ n $ houses and $ n-1 $ road. From each house, you can get to the other by moving only along the roads. That is, the city is a tree. Vlad lives in a house with index $ x $ , and Nastya lives in a house with index $ y $ . Vlad decided to visit Nastya. However, he remembered that he had postponed for later $ k $ things that he has to do before coming to Nastya. To do the $ i $ -th thing, he needs to come to the $ a_i $ -th house, things can be done in any order. In $ 1 $ minute, he can walk from one house to another if they are connected by a road. Vlad does not really like walking, so he is interested what is the minimum number of minutes he has to spend on the road to do all things and then come to Nastya. Houses $ a_1, a_2, \dots, a_k $ he can visit in any order. He can visit any house multiple times (if he wants).

输入输出格式

输入格式

The first line of input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of input test cases. There is an empty line before each test case. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le k \le n \le 2\cdot 10^5 $ ) — the number of houses and things, respectively. The second line of each test case contains two integers $ x $ and $ y $ ( $ 1 \le x, y \le n $ ) — indices of the houses where Vlad and Nastya live, respectively. The third line of each test case contains $ k $ integers $ a_1, a_2, \dots, a_k $ ( $ 1 \le a_i \le n $ ) — indices of houses Vlad need to come to do things. The following $ n-1 $ lines contain description of city, each line contains two integers $ v_j $ and $ u_j $ ( $ 1 \le u_j, v_j \le n $ ) — indices of houses connected by road $ j $ . It is guaranteed that the sum of $ n $ for all cases does not exceed $ 2\cdot10^5 $ .

输出格式

Output $ t $ lines, each of which contains the answer to the corresponding test case of input. As an answer output single integer — the minimum number of minutes Vlad needs on the road to do all the things and come to Nastya.

输入输出样例

输入样例 #1

3

3 1
1 3
2
1 3
1 2

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

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

输出样例 #1

3
7
2

说明

Tree and best path for the first test case:  $ 1 \rightarrow 2 \rightarrow 1 \rightarrow 3 $ Tree and best path for the second test case:  $ 3 \rightarrow 1 \rightarrow 3 \rightarrow 5 \rightarrow 2 \rightarrow 5 \rightarrow 6 \rightarrow 5 $ Tree and best path for the third test case:  $ 3 \rightarrow 5 \rightarrow 2 $