Woburn Challenge 2018-19 Round 3 - Senior Division
Problem 2: Gym Tour
It's every Pokémon trainer's dream to visit all of the Pokémon gyms in their region, defeating each of their gym leaders and claiming gym badges proving their worth! The members of Team Rocket also dream of visiting all of the gyms, though that's mostly because they're sure to be filled with powerful Pokémon worth stealing…
A certain region has N (2 ≤ N ≤ 100,000) towns, numbered from 1 to N. There are N − 1 routes running amongst the towns, each of which allows travelers to walk in either direction between a pair of towns, such that each town may be reached from any other town by following a sequence of one or more routes. The i-th route runs between towns Ai and Bi (1 ≤ Ai, Bi ≤ N, Ai ≠ Bi).
There are K (1 ≤ K < N) Pokémon gyms in the region, the i-th of which is located in town Gi (2 ≤ Gi ≤ N). No two gyms are in the same town, and none of the gyms are in town 1.
Team Rocket would like to pay a friendly visit to each gym's town at least once. They currently find themselves in town 1, and it takes them one whole day to walk along a route from their current town to another town. It takes them no time to conduct any business in the gyms, but all of this walking looks to be very time-consuming by itself!
Fortunately, another potential method of travel is also available to them. A winged Pokémon named Dragonite can be found in town F (1 ≤ F ≤ N), and Team Rocket may be able to enlist its transportation services. If they're ever in town F, they may choose to catch Dragonite. Anytime after they've caught Dragonite, they may choose to Fly back to any town they've previously visited. Catching Dragonite and Flying to a previous town each take no time at all. It's guaranteed that Dragonite is not at a town which has a Pokémon gym.
What's the minimum number of days required for Team Rocket to visit all K gyms after beginning in town 1?
In test cases worth 9/20 of the points, F = 1.
The first line of input consists of three space-separated integers, N, K, and F.
The next line consists of integers, G1..K.
N − 1 lines follow, the i-th of which consists of two integers, Ai and Bi, for i = 1..(N − 1).
Output a single integer, the minimum number of days required for Team Rocket to visit all K gyms.
Sample Input 1
4 3 1 3 4 2 1 2 3 2 4 2
Sample Output 1
Sample Input 2
5 2 4 2 5 1 2 2 3 3 4 1 5
Sample Output 2
Sample Input 3
7 3 2 7 6 3 5 6 4 7 2 4 1 4 6 1 4 3
Sample Output 3
In the first case, Team Rocket can immediately catch Dragonite in town 1. They can then walk to town 2 followed by town 3, visiting both of their gyms. They can then Fly back to town 2, and finally walk from there to town 4 to visit its gym. In total, they will have walked from town to town 3 times, resulting in the whole tour taking 3 days.
In the second case, Team Rocket can begin by walking to town 2 and visiting its gym. They can then walk back to town 1 and then to town 5, visiting its gym as well.
Point Value: 12 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Feb 01, 2019
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3