Vlad and Unfinished Business Codeforces Solution | Codeforces Problem Solution 2022

Vlad and Unfinished Business Codeforces Solution | Codeforces Problem Solution 2022

 F. Vlad and Unfinished Business

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Vlad and Nastya live in a city consisting of 𝑛$n$ houses and 𝑛−1$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$1$ minute, he can walk from one house to another if they are connected by a road.

Solution Click Below:- CLICK HERE

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 𝑎1,𝑎2,…,𝑎𝑛$a_1,a_2,\dots ,a_n$ he can visit in any order. He can visit any house multiple times (if he wants).

Input

The first line of input contains an integer 𝑡$t$ (1≤𝑡≤104$1\le t\le {10}^4$) — the number of input test cases. There is an empty line before each test case.

Food for Animals Codeforces Solution | Codeforces Problem Solution 2022 

Make It Increasing Codeforces Solution | Codeforces Problem Solution 2022 

Detective Task Codeforces Solution | Codeforces Problem Solution 2022 

Vertical Paths Codeforces Solution | Codeforces Problem Solution 2022 

Replace With the Previous, Minimize Codeforces Solution 

Vlad and Unfinished Business Codeforces Solution 

Sorting Pancakes Codeforces Solution 

The first line of each test case contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑘≤𝑛≤2⋅105$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≤𝑥,𝑦≤𝑛$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 𝑎1,𝑎2,…,𝑎𝑘$a_1,a_2,\dots ,a_k$ (2≤𝑎𝑖≤𝑛$2\le a_i\le n$) — indices of houses Vlad need to come to do things.

The following 𝑛−1$n-1$ lines contain description of city, each line contains two integers 𝑣𝑗$v_j$ and 𝑢𝑗$u_j$ (1≤𝑢𝑗,𝑣𝑗≤𝑛$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⋅105$2\cdot {10}^5$.

Output

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.

Join Now for Solution:-