• 동적 연결성 문제와 경로 합 쿼리를 합쳐놓은 문제
• 엣지를 추가해나가면서 어떤 두 노드가 연결되어있는지를 체크하는 것은 동적 연결성 에서 설명했듯, Disjoint Set을 사용해서 처리 가능하다.
• 경로 합 쿼리는 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
  • teflib.disjointset.DisjointSet
  • teflib.fenwicktree.FenwickTree
  • teflib.ttree.HeavyLightDecomposition