CCC '16 S3 - Phonomenal Reviews

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 3.0s
Memory limit: 128M

Author:
Problem type

Jo is a blogger, specializing in the critique of restaurants. Today, she wants to visit all the Vietnamese Pho restaurants in the Waterloo area, in order to determine which one is the best.

There are N restaurants in the city of Waterloo, numbered 0 to N-1. However, only M of them are Pho restaurants. Jo can choose to start at any restaurant. There are N-1 roads in Waterloo, each road connecting exactly two restaurants. It is possible to reach every restaurant from any restaurant using these roads. It takes Jo exactly 1 minute to travel along any road.

In computer science, a road network with this structure is called a tree. Here are three examples of trees:

One property that is true for all trees is that there is exactly one path that does not repeat any roads between any two points in the tree.

What is the minimal length of time that Jo needs to spend on traveling on roads to visit all of the Pho restaurants?

Input Specification

The first line of input contains 2 integers, N and M (2 \le M \le N \le 100\,000).

The second line of input contains M distinct integers indicating the restaurants which are Pho restaurants.

The next N-1 lines contain 2 integers each. The i^{th} line contains a_i and b_i, (0 \le a_i, b_i \le N-1), representing a path between the two restaurants numbered a_i and b_i.

  • For 3 of the 15 available marks, M = 2 and N \le 100.
  • For an additional 3 of the 15 available marks, M \le 3 and N \le 100.
  • For an additional 3 of the 15 available marks, M \le 8 and N \le 100.
  • For an additional 4 of the 15 available marks, M \le N \le 1\,000.

Output Specification

Your program should output one line, containing one integer - the minimum amount of time Jo needs to spend traveling on roads in order to visit all Pho restaurants, in minutes.

Sample Input 1

8 2
5 2
0 1
0 2
2 3
4 3
6 1
1 5
7 3

Output for Sample Input 1

3

Explanation for Output for Sample Input 1

The path between 5 and 2 goes through 5 \rightarrow 1 \rightarrow 0 \rightarrow 2, which uses 3 roads.

Sample Input 2

8 5
0 6 4 3 7
0 1
0 2
2 3
4 3
6 1
1 5
7 3

Output for Sample Input 2

7

Explanation for Output for Sample Input 2

If Jo begins at restaurant 6, she will only need to use 7 roads. One possible path that she can take is: 6 \rightarrow 1 \rightarrow 0 \rightarrow 2 \rightarrow 3 \rightarrow 7 \rightarrow 3 \rightarrow 4. Notice that she doesn't need to visit restaurant 5, since it is not a Pho restaurant. A diagram of the road network is shown below:


Comments


  • 0
    ThatGuyOnTheStreet  commented on Feb. 3, 2019, 3:38 p.m.

    The tree examples look like they are trying to spell something


  • 4
    septence123  commented on Dec. 20, 2016, 8:20 p.m.

    When I submitted in PYPY2 I got an invalid return for batch 7 case #2.


  • 5
    r3mark  commented on March 21, 2016, 9:22 a.m.

    I tried resubmitting an old code of mine and it took over three times as long to run (6.36s to 22.77s).


    • 3
      Xyene  commented on March 21, 2016, 9:47 a.m.

      We'll look into it, thanks. We're experimenting with an Embedded JRE for running Java 8 on one judge - this might explain the faster speed for one, but I'll double-check this to make sure.


  • 4
    fifiman  commented on Feb. 20, 2016, 9:42 a.m.

    Isn't the answer 7, and not 3?


    • 4
      kobortor  commented on Feb. 20, 2016, 9:49 a.m.

      fixed


      • 3
        Xyene  commented on Feb. 20, 2016, 10:42 a.m.

        Thanks; the problem statements are manually typed up due to the present lack of official PDF versions. As such, there might exist typos here and there.