티스토리 뷰
문제: http://www.ioi2013.org/wp-content/uploads/tasks/day1/dreaming/Dreaming ko (KOR).pdf
$N-M-1$개의 간선을 새로 추가하고 나서 답이 될 수 있는 경우는 다음과 같다.
- 기존의 트리에 있는 최장 경로
- 새로운 간선이 포함되는 최장 경로
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 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- idea
- IOI2012
- HackerRank
- ioi
- BOI
- BOI 2001
- USACO
- optimization
- Algorithm
- Boyer
- Divide & Conquer
- Greedy Method
- IOI2013
- Dynamic Pramming
- moore
- Segment tree
- majority
- Parametric Search
- Tree
- IOI2014
- vote
- Dijkstra
- Boyer-Moore Majority Vote Algorithm
- BOI 2009
- Splay Tree
- dynamic programming
- z-trening
- IOI2011
- Knuth Optimization
- TRIE
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함