동적 연결성

쿼리 종류에 따라서 '엣지를 추가하는 쿼리만 들어올 때' / '엣지를 삭제하는 쿼리만 들어올 때' / '두 종류의 쿼리가 모두 들어올 때' 로 분류

그래프 종류에 따라서 '트리' / '일반 그래프' 로 분류

'오프라인 쿼리로 처리 가능한 경우' / '오프라인 쿼리로 처리가 불가능한 경우' 로 분류

엣지를 추가하는 쿼리만 들어올 때 → 가장 쉽다. Disjoint Set으로 해결 가능.

오프라인 쿼리로 처리 가능하고 엣지를 삭제하는 쿼리만 들어올때. → 역순으로 업데이트해나가면 엣지를 추가하는 쿼리만 들어오는 경우랑 동일해짐

트리일 때 → 문제에 따라 다양한 방법이 존재. Link-Cut tree 등으로 해결 가능

오프라인 쿼리로 처리 가능한 경우 → '오프라인 동적 연결성'이라고 불리는 문제. 분할 정복과 롤백을 지원하는 Disjoint Set을 함께 사용하는 방법이 있다

추가시키는 엣지들로 트리를 '잘' 만들고, 쿼리들을 트리에서의 LCA나 경로최댓값으로 처리하는 방법이다. 쿼리들을 온라인으로 처리 가능

오프라인 쿼리가 가능할때에는 쿼리들을 small-to-large 테크닉으로 관리하며 풀 수 있다. 컴포넌트마다 대응되는 쿼리들을 유지하고, 컴포넌트가 합쳐질때마다 해당되는 쿼리들을 해결하는 방법이다.

역시 오프라인 쿼리가 가능할때에는 병렬 이분 탐색 (Parallel Binary Search; PBS)을 써서도 풀 수 있다.

오프라인/small-to-large : 732ms https://www.acmicpc.net/source/53524779

온라인/트리 LCA : 1432ms https://www.acmicpc.net/source/53524158

온라인/트리 경로최솟값쿼리 (binary jumping) : 1868ms https://www.acmicpc.net/source/53521655

오프라인/PBS : 3912ms https://www.acmicpc.net/source/53525864

이 문제에서는 엣지에 가중치를 줘야 해서, 노드에 가중치를 주는 문제들에 비해서 LCA가 좀더 불리했다.

예를 들면 16704

[오프라인 쿼리] O(n+q*α(n)) < [서브트리쿼리 + 펜윅트리] (O(n+qlogn)) < [경로쿼리 + 펜윅트리] (O(n+qlog^2n)) < [서브트리쿼리 + 레이지 세그트리] (O(n+qlogn)) < [노드값 일일히 바꾸기] (O(n+q+nlogn)) 순서였다.

[노드값 일일히 바꾸기] 방법은 열심히 최적화를 시도했지만 TLE 벗어나지 못했다.

여기서 주의할 점은, assignment update를 써서 서브트리 전체를 동일한 값으로 할당해주면 안된다. 서브트리 안에서 이미 이전에 엣지 삭제 연산이 처리되어서 서브트리 안의 노드들이 여러가지 그룹ID를 갖고 있을 수 있다. parent[u]와 그룹ID가 같은 노드들에게만 새 그룹 ID를 할당해주어야만 한다. (안그러면 서브트리 안에서 이전에 쪼갠 그룹들이 다시 합쳐지게 된다.) 이것을 처리하는 방법은 새 그룹 ID를 u의 DFS ordering으로 만들어서 max update를 해주는 것이다. 그러면 서브트리 안에서 쪼개져있던 그룹들은 u의 DFS ordering보다 더 큰 그룹 ID를 갖고 있었을테니, max 연산으로는 바뀌지 않는다.

이렇게 max 업데이트를 사용하면 lazy segment tree를 사용해서, 엣지 삭제와 연결성 체크를 각각 O(logn)에 할수 있다.

구간 합으로 처리하는 방법은, 그냥 u이하의 노드들의 그룹ID에 전부 특정 값을 더해주는 것이다. 이러면 u이하의 노드들 중 그룹ID가 달랐던 노드들은 업데이트 이후에도 그룹 ID를 다르게 갖는다. 문제가 되는 것은 관계 없는 노드들이 우연히 같은 ID를 갖게 되는 것이다. 예를 들어 그냥 항상 1을 더해주기로 했다고 하자. 노드 s가 차일드 u, v를 갖고 있을때, (s,u)와 (s,v)를 모두 끊으면, s와 v, 또 s와 u는 다른 그룹ID를 갖지만, u와 v가 같은 ID를 갖게 되어서 연결된 것으로 처리된다. 이것을 방지하기 위해, 새로 값을 더해 만들어진 그룹ID가 기존에 존재하지 않았던 ID가 되게 하려면 매번 업데이트 할때마다 더하는 값을 1,2,4,8,.. 이렇게 늘려갈 수도 있지만 이렇게 하면 업데이트 몇번만 하면 그룹 ID값이 너무 커진다.

대신에 u와 v의 그룹 ID가 같더라도 실제로 연결된 것이 맞는지를 확인하기 위해 추가로 lca(u,v)의 그룹 ID를 같이 체크해주는 방법이 있다. 이 세 노드가 모두 같은 그룹 id를 가질때만 연결된 것으로 체크하면 된다.

좀더 기발한? 방법은.. 그냥 업데이트하는 값을 랜덤으로 정하는 것이다. 이때는 group ID의 최댓값을 고정시키려면 덧셈보다 XOR을 쓰는 것이 낫다. 그냥 int 범위에서 랜덤값을 만들어서 업데이트한다고만 생각해보자. 보통 문제들에서는 트리의 크기가 몇십만 단위이고, 모든 엣지가 다 끊어져서 각각이 전부 다른 그룹ID를 가져야 하는 상황이라고 쳐도, 몇십만개의 랜덤값중 같은 값이 확률은 가능성은 매우 낮다. 우연히 같은 값을 갖는 노드들이 있더라도 그 노드들에 대한 연결성 쿼리가 들어올 확률은 또 낮다. 이 방법을 쓰면 Lazy propagation을 처리할 필요도 없고 LCA를 계산할 필요도 없고 그냥 XOR펜윅트리 하나만으로 풀 수 있다.