티스토리 뷰

IOI/IOI2013

[IOI2013 Day1] Dreaming 해법

전명우 2013.07.22 00:52

문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/dreaming/Dreaming ko (KOR).pdf

$N-M-1$개의 간선을 새로 추가하고 나서 답이 될 수 있는 경우는 다음과 같다.

  1. 기존의 트리에 있는 최장 경로
  2. 새로운 간선이 포함되는 최장 경로

1번 경우를 계산하기 위해, 우리는 트리 내의 최장 경로의 길이를 구해야한다. 트리 내에 최장 경로를 트리의 '지름'이라고 말한다. 트리의 지름 구하는 방법은 여러가지가 존재하는데, 그 중 하나는 어떤 한 정점을 잡고, 그 점과 가장 먼 점 $v$를 찾고, 다시 $v$ 에서 제일 먼 경로를 찾으면 그 경로가 트리의 지름이 된다. 처음에 기존에 있는 트리들의 지름을 구하고 답으로 갱신한다.

2번 경우 해결을 위한 설명의 편의상 트리의 '반지름'을 정의하겠다. 어떤 정점 $v$와 가장 먼 정점과의 거리들 중 최소 길이를 '반지름의 길이'라 하며 이 때 정점 $v$를 트리의 '중심'이라 정의하겠다. 입력으로 주어진 트리들의 반지름 길이를 내림차순으로 정렬한다.

반지름들을 $r_1$ ≥ $r_2$ ≥ ... ≥ $r_k$ 라고 하자.

$k>1$인 경우, $r_1+r_2+L$을 답으로 갱신해주고
$k>2$인 경우, $r_2+r_3+2L$을 답으로 갱신해준다.

즉, $r_1$의 중심 노드와 각 트리의 중심 노드를 연결해준 꼴이 된다.
중심들끼리 연결해야 됨은 자명하고, 중심들을 이처럼 연결해주는 것이 2번 경우 최대값을 최소화 할 수 있음은 쉽게 증명된다.

코드 보기

신고

'IOI > IOI2013' 카테고리의 다른 글

IOI2013 잡담  (2) 2013.07.22
[IOI2013 Day2] Game 해법  (2) 2013.07.22
[IOI2013 Day2] Robots 해법  (0) 2013.07.22
[IOI2013 Day2] Cave 해법  (0) 2013.07.22
[IOI2013 Day1] Wombats 해법  (0) 2013.07.22
[IOI2013 Day1] Dreaming 해법  (2) 2013.07.22
댓글
댓글쓰기 폼