두 번째 트리의 지름
시간 제한1초메모리 제한1024 MB
가중치가 있는 정점 10만 개 이하의 트리에서 두 번째로 먼 두 정점 사이의 거리를 구한다. 지름과 같은 값이 나와도 된다.
문제
트리에 N개의 정점이 있고, 각 정점에는 1부터 N까지의 번호가 붙어 있다.
트리에서 가장 먼 두 정점 사이의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 흔하므로, 이번에는 두 번째 트리의 지름을 구하려고 한다.
두 번째 트리의 지름이란 두 번째로 먼 두 정점 사이의 거리를 말한다. 두 번째 트리의 지름은 트리의 지름과 같을 수 있다.
두 번째 트리의 지름을 구해 보자.
입력
첫째 줄에 정점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N번째 줄까지 각 간선의 정보가 주어진다. 간선의 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수와 두 번째 정수는 간선으로 연결된 두 정점의 번호이고, 세 번째 정수는 간선의 가중치이다. 간선의 가중치는 20,000 이하의 자연수이다.
출력
첫째 줄에 두 번째 트리의 지름을 출력한다.