Tree Diameter and Critical Edges

A tree is an undirected connected acyclic graph with N nodes and N-1 edges. Each edge has a positive integer weight. Given such a tree, the distance between two nodes a and b is defined as the sum of the weights of the unique simple path between them. The diameter of the tree is the maximum distance among all pairs of nodes (note that there may be more than one diameter path).

An edge is called critical if it is contained in every diameter of the tree. Your task is to compute D, the length of the diameter, and the number of critical edges, i.e. the number of edges that occur in every diameter.

Insight: In a tree the simple path between two given nodes is unique. Let A and B be two endpoints of one diameter. Obviously, every diameter must use some subset of edges on the unique path from A to B. However, if an off‐branch (a branch off the A–B path) has an alternative route, then a diameter not using some edge on A–B may exist. In particular, for each edge e on the A–B path, if after removal of e one of the two separated components has an internal diameter equal to D (the overall diameter), then there is a diameter that avoids e, and e is not critical. Otherwise, if neither component can achieve a diameter of D by itself, e is critical.

Note on calculations: Suppose the unique A–B path is p[0]=A, p[1], ..., p[k]=B with cumulative distances from A. For each vertex u on this path, let branch(u) be the maximum distance from u into the subtree attached to u (ignoring neighbors on the A–B path) and let off_diam(u) be the diameter of that off‐branch subtree. Then for every vertex u on the path, one candidate for an alternative diameter in the component (if the edge is removed) is dist_A(u)+branch(u) (where dist_A(u) is the distance from A to u) and also off_diam(u) may contribute. By precomputing prefix maximums (from A’s side) and suffix maximums (from B’s side) of these values, one may decide for each edge e joining p[i] and p[i+1] that if both maximum values in the corresponding components are less than D, then every diameter must use e.

inputFormat

The first line contains an integer N (the number of nodes).

Each of the following N-1 lines contains three integers u v w, indicating there is an edge between node u and node v with weight w (1-indexed).

It is guaranteed that the given graph is a tree.

outputFormat

Output two integers separated by a space: the length of the diameter, and the number of critical edges (edges that appear in every diameter).

sample

3
1 2 1
2 3 1

2 2