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 A_i and B_i (1 ≤ A_i, B_i ≤ N, A_i ≠ B_i).

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

Subtasks

In test cases worth 9/20 of the points, F = 1.

Input Format

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

Output Format

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

3

Sample Input 2

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

Sample Output 2

3

Sample Input 3

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

Sample Output 3

5

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.

All Submissions
Best Solutions

Point Value: 12 (partial)
Time Limit: 3.00s
Memory Limit: 64M
Added: Feb 01, 2019
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I made the mistake of submitting my solutions to I3 and I4 to S1 and S2 after getting stuck, unaware of the consequences of submitting to two divisions. At the time, I was thinking of practicing the Senior after completing the Intermediate division.

I placed 4th out of High School participants in the Intermediate contest and only 24th in the Senior competition. I was just wondering if I am still eligible for prize qualification in the Intermediate division. All my solutions in the Intermediate division were completed and submitted before then submitting them to the Senior division. 

I hope that I can still receive recognition for my results in this round, though I understand that this would be an exception to established rules, and greatly regret my actions during the contest. 

I made contact by email yesterday but haven't received a reply, and I'm quite desperate to resolve this issue.

Thanks in advance for your help!

Hi there, thanks for reaching out. We have replied to your email. Please take a look.