thdwngjs1108   7달 전

BOJ 6759번 – LHC

시간 제한: 2초 | 메모리 제한: 512MB

문제

최신 극비 실험을 위해 대량의 힉스 보손이 필요합니다. 이 입자를 얻으려면 거대 강입자 충돌기(Large Hadron Collider), 즉 입자를 가속하여 서로 충돌시킬 수 있는 긴 원형 터널을 건설해야 합니다.

이미 광범위한 터널 네트워크에 접근할 수 있으며, 이 네트워크는 연결되어 있고 순환 경로가 없음이 보장됩니다. 즉, 기존 터널은 트리 구조를 이룹니다. 이 시스템은 1부터 N까지 번호가 매겨진 N개의 교차점과, 두 교차점을 연결하는 N−1개의 터널로 표현됩니다. 터널은 양방향으로 통행할 수 있습니다.

네트워크에 정확히 하나의 터널을 추가하면 순환 경로를 만들 수 있고, 이것이 강입자 충돌기가 됩니다. 이때 가능한 한 가장 긴 충돌기를 만들고자 하며, 길이는 순환 경로에 포함된 터널의 수로 정의합니다. 또한, 이를 달성하는 방법의 수도 구해야 합니다. 즉, 두 교차점 사이에 터널을 추가했을 때 최대 길이의 순환이 만들어지는 서로 다른 교차점 쌍의 수를 구하세요.

예를 들어, 아래 네트워크에서 교차점 1과 5 사이, 또는 2와 5 사이에 터널을 건설하면 길이 4의 충돌기를 만들 수 있습니다.

preview

입력

첫 번째 줄에 교차점의 수 N이 주어집니다 (3 ≤ N ≤ 400,000). 다음 N−1개의 줄에는 각각 공백으로 구분된 두 정수 i, j가 주어지며, 교차점 i와 j 사이에 터널이 있음을 나타냅니다 (1 ≤ i, j ≤ N).

출력

한 줄에 두 개의 공백으로 구분된 정수를 출력합니다: 가능한 가장 긴 충돌기의 길이와, 그 길이를 달성하는 방법의 수. 답을 저장하기 위해 64비트 정수가 필요할 수 있습니다.


클로드 활용해서 번역했습니다.

pacto7107   7달 전

요약하면, 트리에서 간선 하나를 추가해서 만들 수 있는 최대 사이클 길이와 그 경우의 수를 구하는 문제입니다. 두 노드 u, v를 연결하면 사이클 길이는 (u와 v 사이의 트리 상 거리) + 1이 되므로, 결국 **트리의 지름(diameter)**을 구하고, 지름과 같은 거리를 갖는 쌍의 수를 세면 됩니다.

라는 말은 클로드가 생성한 것 같은데요......

thdwngjs1108   7달 전

확인도 안하고 올렸네요 수정완료했습니다

댓글을 작성하려면 로그인해야 합니다.