https://www.acmicpc.net/problem/1167
- 2월동안 187문제 풀기(지난달 누적 87개) (66/187)
- 요거 풀면 1967번도 공짜
- 트리의 지름은 아무 점에서나 DFS로 가장 먼 점 A를 찾고를
- 그 A에서 가정 먼 점 B를 찾으면 지름이 된다.
- 증명 : 어떤 점 S에서 가장 먼 점은 트리의 지름의 양 끝점 중 하나이다.
- S에서 가장 먼점 A를 찾고 이게 지름의 양 끝점(X1,X2) 둘 다가 아니라고 하면
dist(S,A) > dist(S,X1) > dist(S,X2)
이 성립하고- 우리는 더 긴 지름
dist(S,A) + dist(S,X1)
을 만들 수 있으므로 모순이다.
1 |
|