Gugu the Raccoon
InterviewTime limit1sMemory limit1024 MB
Given a weighted tree rooted at node 1, find the maximum distance from node 1 to any other node.
Problem
Gugu the raccoon lives in Teletubby Land, and his house has N rooms: an entrance, a living room, a kitchen, a main room, a study, an exercise room, a music room, a food storage room, and so on. Every room, including the entrance, is numbered from 1 to N, and the entrance is room 1. There is exactly one entrance into Gugu's house, and the entrance and all rooms are connected by a total of N-1 paths, so one can travel between any two of them.
Gugu found a melon-flavored ice cream in Smurf Land. To escape the hot summer sun, Gugu wants to hide the ice cream in the room farthest from the entrance.
Find the distance Gugu travels from the entrance of his house to the room where he wants to hide the melon-flavored ice cream.
Input
The first line gives the integer N (1 ≤ N ≤ 5,000).
The next N-1 lines give information about all the paths in Gugu's house as integers A, B, C (1 ≤ A, B ≤ N, 1 ≤ C ≤ 1,000,000,000).
This means the path connecting room A and room B in both directions has length C.
Output
Find the distance Gugu travels from the entrance of his house to the room where he wants to hide the melon-flavored ice cream.