마라톤 코스 3초 1024MB
문제
N개의 마을과 마을 간에 이동 할 수 있는 N-1개의 양방향 도로가 있다. 이 때, 모든 마을에서 다른 모든 마을까지 이동이 가능하다.
마을 사이의 거리는 이용해야 하는 최소 도로의 수로 정의한다.
당신은 마라톤 코스를 계획하고 있으며, 1개의 도로를 철거하고 1개의 도로를 건설하여 가장 긴 마라톤 코스를 만들고 싶다.
건설 한 후에도 모든 마을에서 다른 모든 마을까지 이동이 가능해야 한다.
1개의 도로를 철거하고 1개의 도로를 건설하여 얻을 수 있는 최장 거리를 구하시오.
입력
첫 줄에 마을의 수 N이 주어진다. (3≤N≤300,000)
다음 N-1줄에 걸쳐 2개의 정수 u, v가 주어진다. 이는 u번 마을과 v번 마을이 도로로 연결되어 있다는 의미다. (1 ≤ u, v ≤ N)
출력
1개의 도로를 철거하고 1개의 도로를 건설하여 얻을 수 있는 최장 거리를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 5점 | N≤10 |
| #2 | 10점 | N≤100 |
| #3 | 15점 | N≤3000 |
| #4 | 15점 | N≤300,000, 도로가 3개 이상 연결된 마을은 최대 한 곳이다. |
| #5 | 55점 | 추가 제약 조건 없음. |
예제 #1
4
1 2
1 3
3 4
3
예제 #2
6
1 2
2 3
2 5
4 5
5 6
5
2-5 마을 사이의 도로를 철거하고, 3-4 마을 사이의 도로를 건설하면 1-2-3-4-5-6 코스가 최장 코스가 된다.
로그인해야 코드를 작성할 수 있어요.