Maximum sum of paths P36665


Statement
 

pdf   zip

thehtml

You are given a tree with n nodes, where each edge has a positive cost. Let x and y be any two adjacent nodes. Define p(x, y) as the maximum cost of all paths (with no repeated nodes) whose first step goes from x to y. Define c(x) as the sum of p(x, y) for all y adjacent to x. Please compute the maximum value of c(x) among all nodes x.

Input

Input consists of several cases. Every case begins with the number of nodes n, followed by n−1 edges, each one with two different nodes and the cost of the edge between them. Assume 2 ≤ n ≤ 105. The nodes are numbered starting at zero. Each cost is an integer number between 1 and 1000. The given graph is always a ‍tree. The number of steps between any two nodes is never larger than 1000.

Output

For every case, print the maximum c(x), and how many nodes x achieve such a value.

Public test cases
  • Input

    2   0 1 100
    3   1 0 10  1 2 20
    4   1 0 10  1 2 20  3 1 30
    6   0 2 20  1 2 50  2 3 100  3 4 30  3 5 40
    

    Output

    100 2
    30 3
    60 1
    220 1
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++