Codah ClubУпражнявай. Изпращай. Напредвай.
Вход
Български
#000415

APIO - Patrol

In a city, there are N villages numbered 1, 2, . . . , 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.


Image: patrol

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.


Image: patrol2

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.


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

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

[b]Constraints
• In 10% of the test cases, N <= 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 <= N <= 100, 000 and 1 <= K <= 2.

Input:
8 1
1 2
3 1
3 4
5 3
7 5
8 5
5 6
Output:
11
Input:
8 2
1 2
3 1
3 4
5 3
7 5
8 5
5 6
Output:
10
Input:
5 2
1 2
2 3
3 4
4 5
Output:
6

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.