12912번 - 트리 수정

N개의 정점으로 이루어진 트리 T가 있다. 트리의 각 정점은 0번부터 N-1번까지 번호가 매겨져 있다.

• 트리에서 임의의 두 정점을 연결하는 단순 경로의 개수는 1개이다.
• 두 정점사이의 거리는 두 정점을 연결하는 단순 경로상에 있는 간선의 가중치의 합이다.
• 트리의 지름은 트리에 존재하는 모든 경로 중에서 가장 긴 것이다.

홍준이는 T에서 간선을 하나 제거하고, 간선을 하나 추가하려고 한다. 이때, 추가하는 간선의 가중치는 제거한 간선의 가중치와 같아야 하며, 간선을 추가한 이후에도 트리를 유지해야 한다.

이때, 홍준이가 만들 수 있는 트리 중에서 지름이 가장 큰 것을 구하는 프로그램을 작성하시오.

첫째 줄에 트리 정점의 개수 N이 주어진다. (2 ≤ N ≤ 2,000)

둘째 줄부터 N-1개의 줄에는 트리를 이루는 간선이 주어진다. 간선은 from, to, cost와 같이 세 가지 정수로 이루어져 있으며, from과 to를 연결하는 간선의 가중치가 cost라는 뜻이다. (1 ≤ cost ≤ 1,000,000,000)

첫째 줄에 홍준이가 만들 수 있는 트리 중에서 가장 지름이 큰 것의 지름을 출력한다.

예제 1의 경우에 트리는 정점이 4개이고, 간선이 3개있다. 입력으로 주어진 트리의 지름은 2와 3을 연결하는 경로이고 거리는 8+4=12이다.

1과 0을 연결하는 간선을 지우고 3과 1을 연결하는 간선을 추가하면, 트리의 지름은 2와 1을 연결하는 경로가 되고, 길이는 8+4+2=14가 된다.

예제 2의 경우에는 간선을 지우고 같은 간선을 추가하는 것이 정답이다.