Problem D
Paimon's Tree
Paimon has found a tree with
Paimon will give you an integer sequence
During the
What’s the maximum length of the diameter of the weighted tree if we select the vertices optimally? The diameter of a weighted tree is the longest simple path in that tree. The length of a simple path is the sum of the weights of all edges in that path.
Input
There are multiple test cases. The first line of the input
contains an integer
The first line contains an integer
The second line contains
For the following
It’s guaranteed that there are at most
Output
For each test case output one line containing one integer indicating the maximum length of the diameter of the tree.
Explanation
For the first sample test case, we select the vertices in
the order of
![\includegraphics[width = 4.5cm]{sample.png}](/problems/paimonstree/file/statement/en/img-0001.png)
Sample Input 1 | Sample Output 1 |
---|---|
2 5 1 7 3 5 4 1 3 2 3 3 4 4 5 4 6 1 1000000000 1 2 |
16 1000000000 |