NOIP '07 P4 - Core of a Tree Net

View as PDF

Submit solution

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

Problem type

Let T=(V, E, W) be an acyclic and connected undirected graph (also known as an unrooted tree), each edge has a positive integer weight, we call T a tree network, where V, E Respectively represent the collection of nodes and edges, W represents the collection of the length of each side, and let T have n nodes.

Definitions
  • Path: There is a unique simple path between any two nodes a and b in the tree network. Let d(a, b) represent the length of the path with a and b as the endpoints, which is the sum of the lengths of the sides on the path. We call d(a,b) the distance between two nodes a,b. The distance from a point v to a path P is the distance from that point to the nearest node on P: d(v, P)=\min\{d(v, u), \text{u is the node on the path P}\}

  • Diameter of the tree network: The longest path in the tree network is called the diameter of the tree network. For a given treenet T, the diameter is not necessarily unique, But it can be proved that the midpoint of each diameter (not necessarily exactly a certain node, it may be inside a certain side) is unique, and we call this point the center of the tree network.

  • Eccentric distance ECC(F): the distance from the node farthest from the path F in the tree network T to the path F, that is ECC(F) = \max\{d(v, F), v \in V\}

Task

For a given tree network T=(V, E, W) and a non-negative integer s, find a path F, which is a path on a certain diameter (both ends of the path are nodes in the tree network) , whose length does not exceed s (can be equal to s), so that the eccentricity ECC(F) is the smallest. We call this path the core of the tree network T=(V,E,W). When necessary, F can degenerate to a node. Generally speaking, under the above definition, there is not necessarily only one core, but the minimum eccentricity is unique.

The figure below shows an example of a tree network. In the figure, A-B and A-C are two diameters with a length of 20. Point W is the center of the treenet, and the length of the EF edge is 5. If s=11 is specified, the core of the tree network is path DEFG (or path DEF), and the eccentricity is 8. If s=0 (or s=1 or s=2), the core of the tree network is node F with an eccentricity of 12.

Input Specification

  • Line 1, two positive integers n and s, separated by a space. n is the number of nodes in the tree network, and s is the upper bound of the length of the core of the tree network. Let the node numbers be 1, 2, \ldots n.
  • Lines 2 to n each contains 3 positive integers separated by spaces, indicating the two endpoint numbers and length of each edge in turn. For example, 2 4 7 means that the length of the edge connecting nodes 2 and 4 is 7.

It's guaranteed that the input forms a valid tree.

Output Specification

One non-negative numbers, the minimum eccentricity under this condition.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

5

Constraints

  • 32\% of the test cases satisfy 5 \leq n \leq 15.
  • 56\% of the test cases satisfy 5 \leq n \leq 80.
  • 80\% of the test cases satisfy 5 \leq n \leq 300, 0 \leq s \leq 1\,000.
  • 90\% of the test cases satisfy 5 \leq n \leq 5\times 10^5, 0 \leq s < 2^{31}, and all lengths are positive integers not exceeding 1\,000.
  • 100\% of the test cases satisfy 5 \leq n \leq 2\times 10^6, 0 \leq s < 2^{31}, and all lengths are positive integers not exceeding 1\,000.

Comments

There are no comments at the moment.