-->
当前位置:首页 > 题库

PROGRAMMING:Straight diameter

Luz5年前 (2021-05-10)题库450
Keven now has a tree. Now Keven wants to know the maximum distance between any two points in the tree. Keven won't do this problem, so ask smart you. If you help him solve this problem, he will make your ranking rise.
The distance between two points in the tree is defined as the sum of path edge weights connecting two points. And each path can not pass more than once.
###Input format:
The first line gives a number n, which represents the number of nodes in the tree( The nodes of the tree are (1-N)
Next, n-1 line, each line gives three numbers u, V and W, which means that there is a path with weight of w between point u and point v.
(N<200000,W<100000000)
###Output format:
Output the maximum distance between any two points on the tree in a row.
###Input example:
Here is a set of inputs. For example:
```in
four
1 2 5
1 3 6
1 4 7
```
###Output example:
The corresponding output is given here. For example:
```out
thirteen
```
###Case explanation
The distance from the third point to the fourth point is the largest, and the maximum value is 13.
![ Case. PNG] (~ / 29557536-5058-40ad-8602-44207003379c. PNG)







answer:If there is no answer, please comment