트리의 무게중심
실버 I의견: 0
마을 계획가 지수는 \(N\)개의 마을과 \(N-1\)개의 도로로 이루어진 트리 구조의 행정 구역을 분석하고 있다.
트리의 무게중심(centroid) 은 해당 노드를 제거했을 때 남은 연결 성분 중 가장 큰 성분의 크기가 \(\lfloor N/2 \rfloor\) 이하인 노드를 말한다. 모든 트리에는 무게중심이 반드시 존재하며, 많아도 두 개이다.
무게중심이 두 개인 경우 더 작은 번호를 출력하여라.
- \(1 \le N \le 100\,000\)
첫째 줄에 마을의 수 \(N\)이 주어진다.
다음 \(N-1\)개의 줄에 도로로 연결된 두 마을의 번호가 공백으로 구분되어 주어진다.
무게중심 노드의 번호를 출력한다. 두 개이면 더 작은 번호를 출력한다.
7
1 2
1 3
1 4
2 5
2 6
3 7
1
노드 \(1\)을 제거하면 나머지 연결 성분의 크기는 최대 \(3\) (\(\{2, 5, 6\}\))이고, \(\lfloor 7/2 \rfloor = 3\) 이하이므로 무게중심은 \(1\)이다.
6
1 2
2 3
3 4
4 5
5 6
3
경로 그래프 \(1\)-\(2\)-\(3\)-\(4\)-\(5\)-\(6\)에서 노드 \(3\)을 제거하면 성분 크기가 \(2\) (\(\{1,2\}\))와 \(3\) (\(\{4,5,6\}\))이고, \(\lfloor 6/2 \rfloor = 3\) 이하이므로 무게중심은 \(3\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
트리의 무게중심
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
트리의 무게중심