NOIP '18 P3 - Constructing Tracks

View as PDF

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types

Given a tree with vertices. Edge of the tree has length . We need to choose edge-disjoint paths such that the length of the path with minimum length is maximized.

Input Specification

The first line contains two integers and denoting the number of vertices and the number of paths to be chosen.

In the following lines, the line contains three positive integers denoting the edge goes from to and has length .

Output Specification

The output contains an integer denoting the maximum possible minimum length of the tracks chosen.

Sample Input 1

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

Sample Output 1

31

Note: the chosen path is the path from vertex 4 to vertex 7.

Sample Input 2

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

Sample Output 2

15

The chosen paths are the path from vertex 1 to vertex 7, vertex 6 to vertex 9, and vertex 8 to vertex 5.

Additional samples can be found here.

Constraints

Test Case Degree of vertex
1 No No Yes
2 Yes
3 Yes No No
4 No Yes
5 Yes No
6 No
7 Yes
8
9 No Yes Yes
10
11
12 No
13
14
15
16
17 No
18
19
20

For all test cases, , , , .