WC '18 Contest 3 S2 - Gym Tour

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.4s
Memory limit: 64M

Problem type
Woburn Challenge 2018-19 Round 3 - Senior Division

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 \le N \le 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 A_i and B_i (1 \le A_i, B_i \le N, A_i \ne B_i).

There are K (1 \le K < N) Pokémon gyms in the region, the i-th of which is located in town G_i (2 \le G_i \le 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 \le F \le 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.

Input Specification

The first line of input consists of three space-separated integers, N, K, and F.
The next line consists of integers, G_{1 \dots K}.
N - 1 lines follow, the i-th of which consists of two integers, A_i and B_i, for i = 1\dots(N - 1).

Output Specification

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


Sample Explanation

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.


There are no comments at the moment.