Codeforces Round #352 (Div. 1) - D. Roads in Yusland

기본적인 전략은 가장 말단에서부터 최소 가중치의 path cover를 선택하는데, 선택한 path cover가 끝이 나는 지점을 기준으로 그 밑에서부터 현재 지점을 넘어서거나 혹은 현재 지점에서부터 시작되는 path cover 중 또 가장 작은 걸 선택하는 것임. 

D(x) : depth가 x의 depth 이하인(x or x의 부모들을 향하는) path cover에 대해 x가 포함된 cover의 weight의 음수값(-weight). 이 커버는 x보다 같거나 더 깊은 곳에서 시작해서 최소한 x의 부모까지는 향함. [S. E]를 이미 선택했는데, S+1 혹은 그 위에서 [S, E]를 다시 또 고려하지 않기 위한 값 정도라고 생각하면 되겠다. 마치 구간에 상수 t를 더할 때, 시작점에서 t더하고, 끝점+1에서 t 빼주듯이.

Priority Queue(x) : 정점 x를 포함하고 깊이가 x 미만인 곳으로 향하는 path cover들의 weight와 end point를 weight 오름차순으로 들고 있음.  end point가 현재 정점의 depth 이상이면 pop.

Priority Queue를 병합할 때에 크기가 작은 걸 큰 쪽에 넣는 것에 주의하여 병합하면 됨. 그렇지 않으면 제곱의 병합 메모리 혹은 연산 횟수가 필요하다.

병합 과정을 naive하게 한 코드 : http://codeforces.com/contest/671/submission/18582401

병합 과정에 신경을 쓴 코드 : http://codeforces.com/contest/671/submission/18581421