Centroid Decomposition

centroid.pdf

저번에 스타트링크에서 잠깐 강의했을 때 사용했던 자료입니다. 만든 시간이 길지 않아서 자료의 질이 그렇게 좋지는 못하네요. (발표 이후 수정은 없었습니다 ㅠ)

일반적인 분할 정복의 사용 예를 떠올리면서, Centroid를 지나는 전체 경로를 한번에 처리하는 것이 도움이 되는 경우가 있는지, 그러한 문제는 어떤 것들이 있는지 생각해 보시는 게 도움이 될 것 같습니다. (사실 이거는 많이 풀어봐야 압니다 ㅋㅋ)

추천 문제는 딱히 생각이 안나는데 난이도 순으로 적자면

http://codeforces.com/contest/321/problem/C 

https://www.acmicpc.net/problem/5820 

http://codeforces.com/gym/100570/problem/F

http://codeforces.com/contest/342/problem/E

https://www.acmicpc.net/problem/13514

https://www.acmicpc.net/problem/13513

https://www.acmicpc.net/problem/13854

트리와 쿼리 시리즈는 여기 아주 간략한 풀이를 적었습니다. http://koosaga.com/135