DMOPC '17 Contest 2 P3 - Bad Bunnies

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

Carrots fear one thing, and one thing alone: bad bunnies.

A lost carrot has found themselves in an unweighted graph with N nodes inside bad bunny territory. The carrot knows a little graph theory and recognizes that this graph is a tree! Currently, they are at node X and needs to get to node Y to escape. However, there are R rabbits, the i^\text{th} of which is on node R_i of the graph. Help this carrot figure out the closest they will ever have to be to a rabbit during their escape.


For all test cases:

1 \le R \le N

1 \le a, b, X, Y, r \le N

Subtask 1 [20%]

1 \le N \le 1\,000

Subtask 2 [80%]

1 \le N \le 200\,000

Input Specification

The first line of input will contain 2 integers, N, and R.
The next N-1 lines of input will contain 2 integers each, a, b, indicating there exists an edge between a and b.
The next R lines of input will each contain a single integer, r, indicating that there is a rabbit at r.
The final line of input will contain two integers, X and Y.

Output Specification

A single integer, the closest the carrot will ever get to a rabbit on the path from node X to Y.

Sample Input

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

Sample Output



There are no comments at the moment.