Tourists (Codeforces 487E)

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

문제 설명은 생략함. HLD + BCC를 섞은 문제로써 헬문제였따..

풀이를 대충 요약하겠다. BCC 파트가 제일 어려웠는데, 지금 열거하는 방법으로 BCC를 트리로 묶어줄 수 있다. 꽤나 스탠다드한 방법이 아닐까 싶다. 익혀두자.

* 1. Cut Vertex + BCC Component가 정점이 된다.

* 2. Cut Vertex와 연결된 BCC Component를 이어줌으로써 트리를 만든다.

* 3. BCC Component에서 DFS Number가 가장 높은 애를 BCC Parent라고 정의한다. 이건 내가 쓴 BCC 알고리즘에서, 처음 새 컴포넌트를 spawn한 노드와 동치라고 할 수 있다.

* 4. 문제 특성상 각각의 노드가 Wi의 집합을 갖고 있는데 각각의 BCC는 BCC Parent를 제외한 모든 원소를 포함하며 Cut Vertex는 자신만을 포함한다.

* 5. 4의 말을 받아서 노드를 대응시키면, cut vertex는 그냥 직접 대응시키고, 아닐 경우에는 BCC 1개에만 속해있기 때문에 그 BCC에 대응시키면 된다. 원소 갱신은 말이 조금 달라지는데, 일단 cut vertex가 아니면 당연히 BCC 하나에만 대응시키면 되고, cut vertex면 자신과, 또 자신과 연결된 BCC에 갱신하면 된다. 정확히는 자신과 연결되었으며 자신을 BCC Parent로 가지지 않은 BCC에만 연결시키면 되고. 그러한 BCC는 한개밖에 없다. (BCC Parent를 굳이 제외시킨 이유다. 아니면 갱신에 O(n)이라..) 해당 정점을 방문할 때, 해당 정점에서 spawn된 노드들은 다 자신을 BCC Parent로 가지니, 해당 정점을 맨 처음 마크한 BCC가, 그러한 유일한 BCC 종류이다. 두개의 노드에 대응시키면 된다.

* 6. 구간 쿼리는 이제 위에 말한 대응법을 가지고 하면 된다. 일단 O(n)에 하자. 이 때 "BCC Parent를 제외한"이라는 말이 조금 중요해진다. 만약에 두 정점의 LCA가 BCC에 걸쳐있으면 BCC Parent 역시 처리해줘야 한다.

* 7. 지금 열거한 것들은 Heavy Light Decomposition이라는 현명한 방법을 통해서 갱신 O(lgn). 쿼리 O(lg^2n)에 가능하다. HLD는 http://theyearlyprophet.com/heavy-light-decomposition.html http://blog.anudeep2011.com/heavy-light-decomposition/ 를 참고.

cpp : http://codeforces.com/contest/487/submission/14257902 열심히 짰다.