엣지를 추가해나가면서 어떤 두 노드가 연결되어있는지를 체크하는 것은 동적 연결성 에서 설명했듯, 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)).