Tree Tasks

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Java 8 1.4s

Memory limit: 128M

Author:

magicalsoup

Problem type

Given a weighted tree with $N$ $N$ vertices and $N-1$ $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$ $N$ $(3 \le N \le 5 \times 10^5)$ $(3 \leq N \leq 5 \times 10^{5})$ , denoting the number of vertices.

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

Output Specification

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

Sample Input

Copy

Sample Output

Copy

14
7

Sample Explanation

The graph is depicted below:

$\text{[math]}$

We can see that the distance between node $4$ $4$ and $5$ $5$ is the greatest distance, thus $14$ $14$ is the 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))$ $min (max (7, 7), max (9, 5), max (14, 0))$ , thus $7$ $7$ is the radius.

Comments

1

sre0x2a commented 78 days ago

I am a bit confused on the definition of radius and the example. The example has the radius calculated along the path of the diameter. The instructions define the radius as, " We say the radius of a tree is the minimum of the maximum distances for all points." Does all points equal all vertices in the tree or only the vertices contained in the diameter? For example why would max(7,1) and max(7,1) not be considered for paths 1->2->5 and 1->2->3->4 in the example? (I understand it does not change the radius as max(7,7) would still produce 7)

4

htoshiro commented 78 days ago ← edit 2 →

The radius is just the minimum distance of the maximum distance of any node on the of the diameter to one of the two diameter endpoints.

ex: If we choose node 2 as the center, since the the diameter is from the path 5-2-3-4, then the radius if the center was 2 would be max(7,7). This can be proven to be the most optimal center.