P3304 [SDOI2013] Diameter

Xiao Q recently learned some graph theory. According to the textbook, we have the following definitions. A tree is an undirected graph that is connected and acyclic, where each edge has a positive integer weight representing its length. If a tree has $N$ nodes, it can be shown that it has exactly $N-1$ edges. Path: In a tree, between any two nodes there exists at most one simple path. We use $\text{dis}(a,b)$ to denote the sum of the lengths of the edges on the path between $a$ and $b$. We call $\text{dis}(a,b)$ the distance between nodes $a$ and $b$. Diameter: In a tree, the longest path is called the diameter of the tree. The tree’s diameter may not be unique. Now Xiao Q wants to know, for a given tree, what the length of its diameter is, and how many edges are traversed by all diameters.

The first line contains an integer $N$, the number of nodes. The next $N-1$ lines each contain three integers $a,b,c$, indicating there is an undirected edge of length $c$ between nodes $a$ and $b$.

Output two lines. The first line contains one integer, the length of the diameter. The second line contains one integer, the number of edges that are traversed by all diameters.

[Sample Explanation] There are two diameters: the path from $3$ to $2$ and the path from $3$ to $6$. Both diameters pass through edge $(3,1)$ and edge $(1,4)$. For $100\%$ of the testdata: $2 \le N \le 2 \times 10^5$, $1 \le a,b \le N$, $0 \le c \le 10^9$. The input graph forms a tree. Translated by ChatGPT 5