APIO '10 P2 - Patrol

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

In a city, there are N villages numbered 1, 2, \ldots, N . There are N - 1 roads connecting them. Each road connects exactly 2 villages, and from any village, one can reach any other village using these roads. The length of each road is 1 unit.

To ensure safety of the people in the city, each day a city police patrol has to travel on every road. The police station is at village 1, so the patrol has to start from village 1 and finally return to village 1 at the end of the day.

Consider the following example of a city with 8 villages below. Villages are shown as circles and village 1 is shown as a black circle. The roads are the lines connecting these villages. To traverse all roads, the patrol has to travel 14 units each day. Note that the patrol must travel along each road twice to complete each day’s job.

To reduce the total distance required, the city plans to build K new shortcuts between these villages. Each shortcut can connect any two villages. Two shortcuts can end at the same village (see example (c) below). A shortcut can even be a loop; that is, connect a village to itself.

Funding is limited, so K is either 1 or 2. Also, to make sure that the city is not wasting money, it is required that the patrol must travel along each shortcut exactly once a day.

Consider the following examples.

In example (a), one shortcut is built, and the total distance is 11. In example (b), two shortcuts are built, and the total distance the patrol has to travel is 10. In the last example (c), two shortcuts are built, however since there is a requirement on the number of times the patrol can travel on each shortcut exactly once, the total distance now becomes 15.

Write a program that reads the information about the roads between the villages and the number of shortcuts to be built and computes the location for the shortcuts that minimizes the total distance the patrol has to travel each day.

Input Specification

The first line of input contains two integers N and K (1 \le K \le 2). The next N - 1 lines contain information about the roads. Each of these lines contains two integers A and B, (1 \le A, B \le N), which says that there is a road connecting village A and village B.

Output Specification

Your program should output one line with an integer which is the minimum distance the patrol has to travel after K shortcuts have been built.

Sample Input 1

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

Sample Output 1

11

Sample Input 2

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

Sample Output 2

10

Sample Input 3

5 2
1 3
2 3
3 4
4 5

Sample Output 3

6

Constraints

  • In 10\% of the test cases, N \le 1\,000 and K = 1.
  • In 30\% of the test cases, K = 1.
  • In 80\% of the test cases, the maximum number of adjacent villages for each village is at most 25.
  • In 90\% of the test cases, the maximum number of adjacent villages for each village is at most 150.
  • In 100\% of the test cases, 3 \le N \le 100\,000 and 1 \le K \le 2.

Comments


  • 1
    Paradox  commented on Sept. 1, 2017, 5:11 p.m.

    Why does Sample Input 1 contain loops?


    • -8
      Kirito  commented on Sept. 2, 2017, 11:48 p.m. edited

      This comment is hidden due to too much negative feedback. Click here to view it.