====== 남극 탐험 ======

===== 풀이 =====
  * [[ps:동적 연결성]] 문제와 [[ps:경로 쿼리#경로 합 쿼리]]를 합쳐놓은 문제
  * 엣지를 추가해나가면서 어떤 두 노드가 연결되어있는지를 체크하는 것은 [[ps:동적 연결성]] 에서 설명했듯, [[ps:Disjoint Set]]을 사용해서 처리 가능하다.
  * [[ps:경로 쿼리#경로 합 쿼리]]는 Heavy Light Decomposition을 비롯, 여러가지 방법으로 풀이가 가능하다. 
  * 문제는 Heavy Light Decomposition을 쓰려면 우선 트리의 구조를 알고 있어야 하는데 그것이 불가능하다는 점.
  * 그것을 오프라인 쿼리 방식으로 해결한다. 먼저 쿼리를 죽 훑으면서 엣지를 추가하는 쿼리들만 처리해본다. 이렇게 해서 만들어진 트리가 최종 트리의 모습이 될 것이므로, 이 트리를 가지고 Heavy Light Decomposition을 돌린다.
    * 이때 최종 상태가 전체가 연결된 tree가 된다는 보장은 없다. forest가 될 수도 있고, 이 경우에는 dfs 한번으로 전체를 훑을수 없다. forest안의 각 tree들에 대해서 따로 Heavy Light Decomposition를 돌릴수도 있겠지만.. 그냥 엣지들을 추가해서 하나의 트리로 합쳐버리는 것이 좀더 구현이 편해 보인다.
  * 이렇게 hld 준비가 끝나면, 아까 사용했던 Disjoint Set을 초기화하고, 다시 쿼리를 처음부터 진행하면서 처리해주면 된다.
    * 엣지 추가와 연결성 체크는 Disjoint Set을 사용해서 O(α(n)), 펭귄수 업데이트와, 경로안의 펭귄수 계산은 HLD와 펜윅트리를 사용해서 O(log^2(n)) 이 걸린다.
  * HLD를 준비하는데에 O(n), 펜윅트리를 초기화하는데에도 O(n). 각 쿼리에 대해서는 최대 O(log^2(n)) 이 걸리므로, 총 시간복잡도는 O(n+qlog^2(n)).

===== 코드 =====
(다이아몬드 이상은 코드 생략)

  * Dependency
    * [[ps:teflib:disjointset#DisjointSet|teflib.disjointset.DisjointSet]]
    * [[ps:teflib:fenwicktree#FenwickTree|teflib.fenwicktree.FenwickTree]]
    * [[ps:teflib:ttree#HeavyLightDecomposition|teflib.ttree.HeavyLightDecomposition]]

{{tag>BOJ ps:problems:boj:다이아몬드_5}}