APIO '10 P2 - Patrol - Olympiads Online Judge

APIO '10 P2 - Patrol

Points: 20 (partial)

Time limit: 0.6s

Memory limit: 64M

Problem type

In a city, there are $N$ ~N~ villages numbered $1, 2, \dots, N$ ~1, 2, \dots, N~. There are $N-1$ ~N-1~ roads connecting them. Each road connects exactly $2$ ~2~ villages, and from any village, one can reach any other village using these roads. The length of each road is $1$ ~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$ ~1~, so the patrol has to start from village 1 and finally return to village $1$ ~1~ at the end of the day.

Consider the following example of a city with $8$ ~8~ villages below. Villages are shown as circles and village $1$ ~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$ ~14~ units each day. Note that the patrol must travel along each road twice to complete each day's job.

$\text{[math]}$

To reduce the total distance required, the city plans to build $K$ ~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$ ~K~ is either $1$ ~1~ or $2$ ~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.

$\text{[math]}$

In example (a), one shortcut is built, and the total distance is $11$ ~11~. In example (b), two shortcuts are built, and the total distance the patrol has to travel is $10$ ~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$ ~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$ ~N~ and $K$ ~K~ $(1 \le K \le 2)$ ~(1 \le K \le 2)~. The next $N - 1$ ~N - 1~ lines contain information about the roads. Each of these lines contains two integers $A$ ~A~ and $B$ ~B~ $(1 \le A, B \le N)$ ~(1 \le A, B \le N)~, which says that there is a road connecting village $A$ ~A~ and village $B$ ~B~.

Output Specification

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

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Constraints

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

Comments

-3

Dan13llljws commented on March 16, 2020, 4:54 p.m. ← edit 2 →

For the sample, if I build a shortcut between 6 and 4, won't the cost be 9 by not travelling the road between 3 and 5, or does the patrol also have to travel all the roads

11

Rimuru commented on March 17, 2020, 1:34 p.m.

To ensure safety of the people in the city, each day a city police patrol has to travel on every road.

4

Dan13llljws commented on March 17, 2020, 3:42 p.m.

thanks, I thought he doesn't after the shortcuts are added, sry