Tree Tasks

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Java 8 1.4s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Given a weighted tree with N vertices and N-1 edges, your task is to find the diameter and radius of the tree.

We say the diameter of the tree is the largest distance between any two points.

We say the radius of a tree is the minimum of the maximum distances for all points.

Input Specification

First line, one integer N (3 \le N \le 5 \times 10^5), denoting the number of vertices.

The next N-1 lines will have three integers u, v, w, (1 \le u, v \le N, 1 \le w \le 10^3, u \ne v) denoting that there is a connection between vertices u and v, with a weight of w.

Output Specification

On separate lines, output the diameter, and the radius of the tree in that order.

Sample Input

1 2 1
2 3 2
3 4 5
2 5 7

Sample Output


Sample Explanation

The graph is depicted below:

We can see that the distance between node 4 and 5 is the greatest distance, thus 14 is diameter.

We can see that the minimum value between the maximum distances along the diameter are \min(\max(7, 7), \max(9, 5), \max(14, 0)), thus 7 is the radius.


There are no comments at the moment.