Maximum sum of paths P36665

Statement

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 ≤ 10⁵. 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

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++