Network Hacking
Time limit1sMemory limit512 MB
Given a weighted tree, cut one edge, then reconnect its two endpoints with an edge of the same weight to maximize the resulting tree's diameter.
- Level
Medium7 of 10
- Topics
- Tree, DFS, Greedy, Dynamic programming
- Solved
- No attempts yet
Problem
There is a computer network of N computers numbered 1 through N. Between them, N-1 lines are installed, each directly connecting two computers. In this network, communication is possible between every pair of computers. That is, starting from any computer and repeatedly following directly connected lines reaches every other computer, so communication is possible.
Each line has a unique time required to send data from one computer directly connected to that line to the other. Therefore, the total transmission time for data sent over several lines is the sum of the transmission times of the lines the data passes through.
When data is transmitted from any computer u to another computer v, the data moves along the path from computer u to computer v whose total transmission time is smallest. That total transmission time becomes the data transmission time between u and v.
The maximum transmission time is defined as the largest value among the data transmission times between any two computers in the network. The value of the computer network is determined by this maximum transmission time. In other words, the smaller the maximum transmission time, the more valuable the network.
Seongwon, who dreams of becoming the world's best hacker, decided that to build his hacking skills he should first practice physical hacking. He had long been unhappy with this network, so he chose it as his target and decided to perform physical hacking. Specifically, he plans to attack this network through the following process.
- Choose one of the lines in the network and cut it.
- Choose two different computers, then install a line with the same transmission time as the line just cut between them.
- Because people must not notice that the network has been attacked, communication must remain possible between all computers after the line is cut and reinstalled.
Seongwon will perform the above process exactly once to reduce the value of this network as much as possible. That is, he will make the single choice that maximizes the maximum transmission time computed after the hack is finished.
Since the number of computers in the network is very large, this must be computed with a program, but Seongwon does not know how to program. Let us help poor Seongwon, who cannot program in the era of the Fourth Industrial Revolution.
Input
The first line gives the number of computers in the network, N (2 ≤ N ≤ 200,000).
From the second line through the N-1 following lines, information about the network's lines is given. Each line gives three positive integers a, b, t (1 ≤ a, b ≤ N, a ≠ b, 1 ≤ t ≤ 107), meaning that a line directly connecting computer a and computer b exists, and that line's transmission time is t seconds.
Output
On the first line, output the maximum possible maximum transmission time when the best hacking is performed.