숲을 관리하는 관리인 보라는 산책로 지도를 손에 들고 있다. 이 지도에는 \(N\) 개의 쉼터가 있고, 쉼터들은 정확히 \(N-1\) 개의 산책로로 이어져 있어 어느 두 쉼터 사이든 단 하나의 길로만 갈 수 있다. 즉, 쉼터와 산책로는 하나의 트리(나무) 구조를 이룬다.

산책로마다 포장 상태와 경사가 달라서, 각 산책로에는 서로 다른 길이가 매겨져 있다. 보라는 방문객에게 "가장 긴 산책 코스"를 안내하고 싶다. 즉, 어떤 두 쉼터를 골라 그 사이를 잇는 길을 따라 걸을 때, 지나는 산책로 길이의 합이 최대가 되도록 하고 싶다.

쉼터와 산책로의 정보가 주어질 때, 두 쉼터를 잇는 길 중 길이의 합이 가장 큰 값을 구하는 프로그램을 작성하라. (이 값은 트리의 지름이라고도 부른다.)

\(1 \le N \le 200{,}000\)

\(1 \le w \le 1{,}000{,}000\)

입력으로 주어지는 그래프는 항상 트리이다.

첫째 줄에 쉼터의 수 \(N\) (\(1 \le N \le 200{,}000\)) 이 주어진다.

다음 \(N-1\) 개의 줄에는 각각 세 정수 \(a\), \(b\), \(w\) 가 주어지며, 이는 쉼터 \(a\) 와 \(b\) 를 잇는 길이 \(w\) 의 산책로가 있음을 의미한다. (\(1 \le a, b \le N\), \(a \ne b\), \(1 \le w \le 1{,}000{,}000\))

주어지는 산책로들은 항상 하나의 트리를 이룬다. \(N = 1\) 인 경우 산책로는 주어지지 않는다.

두 쉼터를 잇는 길의 길이 합 중 가능한 최댓값을 한 줄에 출력한다. \(N = 1\) 인 경우 \(0\) 을 출력한다.

riseoj 작성

출처 Original