Diameter of a Tree
InterviewTime limit2sMemory limit128 MB
Given a weighted tree of up to 10,000 nodes rooted at node 1, compute the maximum-length path between any two nodes.
Problem
A tree is a connected undirected graph with no cycles. In a tree, there is exactly one simple path between any two nodes.
The length of a path between two nodes is the sum of the weights of the edges on that path. The diameter of a tree is the maximum path length among all pairs of nodes in the tree.
You are given a weighted tree whose nodes are numbered from 1 to n. The root is node 1, and each edge is described by its parent node, child node, and edge weight. Write a program that computes the diameter of the tree.
Input
The first line contains the number of nodes n (1 ≤ n ≤ 10,000).
Each of the next n-1 lines contains information about one edge. Each line has three integers: the parent node number, the child node number, and the edge weight, in that order. Edge information is given in increasing order of parent node number; if the parent node numbers are the same, it is given in increasing order of child node number.
The root node is always node 1. Every edge weight is a positive integer not greater than 100.
Output
Print the diameter of the tree on the first line.