THICC '17 P6 - Tunnels

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.3s
Java 8 1.0s
Python 1.4s
Memory limit: 256M

Author:
Problem type

On yet another of his adventures, Brian Bipai loses his way in an underground network of tunnels. Fortunately, he brought a map with him.

The map of the tunnel system identifies a series of N points labelled from 1 to N. There are N-1 tunnels that each connect a distinct pair of points (A, B) with a distance of C. Each point can be reached from any other point by exactly one pathway of tunnels.

Brian Bipai does not know which of the points on the map he is located at. He knows that an exit must exist somewhere, but not where it is. However, he observes (based on his nearby surroundings) that he is definitely located at a point with T connecting tunnels.

Brian Bipai would like you to determine all points on the map where he could potentially be at. Furthermore, for each of those points P_i, determine the minimum distance D_i that he has to travel in order to optimally search the entire underground network of tunnels for the exit.

Constraints

1 \le N \le 200\,000

1 \le T \le N-1

1 \le A_i, B_i \le N

1 \le C_i \le 5\,000

For 50\% of the points, 1 \le N \le 2\,000.

Input Specification

The first line contains two integers N and T.

The following N-1 lines each contain three spaced integers: A_i, B_i, and C_i.

Output Specification

For each possible point that Brian Bipai could be at, print P_i and D_i separated by a space on its own line. All P_i must be stated in increasing order.

Sample Input

6 3
1 3 1
2 3 1
3 4 3
4 5 2
4 6 2

Sample Output

3 13
4 14

Explanation

Brian Bipai could be located at point 3 or point 4.
If he begins at point 3, then his optimal search path would be 3 \to 1 \to 3 \to 2 \to 3 \to 4 \to 5 \to 4 \to 6, taking a total distance of 13.
If he begins at point 4, then his optimal search path would be 4 \to 5 \to 4 \to 6 \to 4 \to 3 \to 1 \to 3 \to 2, taking a total distance of 14.


Comments

There are no comments at the moment.