Informatica Online Judge

  트리 마을의 앙숙 [1234 / 04D2]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 85   Total Tried : 97


The Champion of this Problem (C++) : gs15089 - ms / 660byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

GSHS는 n개의 지점과 n-1개의 도로로 연결된 마을이다.

이 마을은 임의의 어떤 지점에서 다른 지점으로 연결된 도로를 이용하여 통행할 수 있다.

이 마을에는 경곽이와 영재가 이사를 온다.

이 두 친구는 조상때부터 서로 사이가 좋지 않았다.

따라서, 서로 최대한 멀리 떨어진 지점의 집을 구하고자 한다.

마을의 도로는 양 방향으로 모두 이동할 수 있으며, 도로 마다 주어진 거리가 있다.

두 지점의 거리는 두 지점 간을 이동할 때 이용하는 도로 길이의 합으로 한다.

마을의 지점과 거리들에 대한 정보가 주어질 때, 경곽이와 영재가 최대한 멀리 떨어진 두 지점에 집을 얻는다고 할 때, 두 지점의 거리를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 지점의 수를 나타내는 정수 n이 입력된다.
두 번째 줄부터 n-1줄에 걸쳐서 각 도로가 연결하는 두 지점과 거리가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 ≤n ≤ 200,000
1 ≤ 각 지점 ≤ n
1 ≤ 각 지점  간 거리 ≤1,000

Output

경곽이와 영재가 집을 구하는 두 지점의 거리를 출력한다. 즉, 가장 멀리 떨어진 두 지점의 거리를 출력한다.

IO Example

입력1
2
1 2 5

출력1
5

입력2
10
1 8 1
8 9 2
6 1 6
1 4 3
1 5 4
5 7 2
1 3 5
3 2 2
3 10 3

출력2
14

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]