# Dynamic MST

Dynamic MST는 그래프의 간선 가중치나 활성 상태가 바뀔 때 minimum spanning tree를 유지하는 주제입니다. 완전한 online dynamic MST는 매우 어렵지만, 대회에서는 "작은 변경은 MST 성질로 갱신"하거나 "질의를 모아서 오프라인으로 처리"하는 형태가 더 자주 등장합니다.

## 문제 신호

| 문제 표현 | Dynamic MST 관점 |
| --- | --- |
| 간선이 추가되고 MST 비용을 묻는다 | cycle property 갱신 |
| 간선 삭제가 섞인다 | replacement edge 탐색 |
| 가중치 업데이트가 있다 | 삭제 후 추가로 분해 |
| 질의를 모두 미리 읽을 수 있다 | offline divide and conquer 후보 |
| 정점 수는 크지만 변경 수가 작다 | periodic rebuild 후보 |

MST는 cut property와 cycle property가 강력합니다. 하지만 삭제된 간선이 MST에 들어 있었는지, 들어 있었다면 어떤 non-tree edge가 대체할 수 있는지를 빠르게 찾는 것이 핵심 난점입니다.

## 간선 추가

현재 MST가 있고 새 간선 `(u, v, w)`가 추가되면, MST 경로 `u..v`에 새 간선을 더해 cycle이 생깁니다.

```text
cycle에서 가장 무거운 간선이 새 간선보다 무거우면 교체
그렇지 않으면 새 간선은 MST에 들어가지 않음
```

따라서 online 추가만 있다면 MST 위 path maximum query가 필요합니다. Link-Cut Tree, Heavy-Light Decomposition, binary lifting rebuild 중 제약에 맞는 것을 고릅니다.

정적 HLD는 tree 교체 뒤 재구축 없이는 쓸 수 없고, 온라인 교체는 LCT 등 동적 tree가 필요합니다.

## 간선 삭제

삭제된 간선이 MST 밖이면 MST는 변하지 않습니다. 삭제된 간선이 MST 안이면 MST가 두 component로 갈라지고, 두 component를 잇는 non-tree edge 중 가장 싼 edge를 찾아야 합니다.

```text
MST edge e 삭제
component A, B로 분리
min weight non-tree edge crossing (A, B)를 replacement로 선택
```

이 replacement edge query가 동적 MST의 어려운 부분입니다. 문제 조건이 약하면 삭제마다 전체 Kruskal을 다시 돌리는 rebuild가 더 안전합니다.

## Rebuild Baseline

아래 코드는 활성 간선 집합에서 MST 비용을 다시 계산하는 기준 구현입니다. 복잡도는 무겁지만, 작은 입력이나 sqrt decomposition rebuild의 내부 루틴으로 유용합니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;

struct DynamicMstBaseline {
    struct Edge {
        int u;
        int v;
        long long weight;
        bool active;
    };

    struct DSU {
        vector<int> parent;
        vector<int> size;

        explicit DSU(int n) : parent(n + 1), size(n + 1, 1) {
            iota(parent.begin(), parent.end(), 0);
        }

        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        bool unite(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b) {
                return false;
            }
            if (size[a] < size[b]) {
                swap(a, b);
            }
            parent[b] = a;
            size[a] += size[b];
            return true;
        }
    };

    int vertexCount;
    vector<Edge> edges;

    explicit DynamicMstBaseline(int n) : vertexCount(n) {}

    int addEdge(int u, int v, long long weight) {
        edges.push_back({u, v, weight, true});
        return (int)edges.size() - 1;
    }

    void setActive(int edgeId, bool active) {
        if (0 <= edgeId && edgeId < (int)edges.size()) {
            edges[edgeId].active = active;
        }
    }

    pair<bool, long long> rebuildMstCost() const {
        vector<Edge> usable;
        for (const Edge& edge : edges) {
            if (edge.active) {
                usable.push_back(edge);
            }
        }
        sort(usable.begin(), usable.end(), [](const Edge& a, const Edge& b) {
            return a.weight < b.weight;
        });

        DSU dsu(vertexCount);
        long long cost = 0;
        int used = 0;
        for (const Edge& edge : usable) {
            if (dsu.unite(edge.u, edge.v)) {
                cost += edge.weight;
                ++used;
            }
        }
        return {used == vertexCount - 1, cost};
    }
};
```

이 baseline은 update마다 `O(N + M log(M+1))`입니다. 하지만 정답 확인용, stress test용, block rebuild용으로는 여전히 가치가 큽니다.

## 오프라인 접근

질의를 모두 읽을 수 있으면 간선의 활성 구간을 만들고 시간 구간별로 안정적인 간선을 분류합니다.

```text
edge e active on [l, r)
divide query time interval
항상 존재하는 edge는 contraction 후보
절대 MST에 못 들어가는 edge는 filtering 후보
```

Dynamic Connectivity에서 쓰는 segment tree over time과 비슷해 보이지만, MST는 가중치 최적화가 끼기 때문에 단순 rollback DSU만으로 끝나지 않습니다. 그래도 "각 구간에서 필요한 edge 후보를 줄인 뒤 재귀"하는 방향은 자주 쓰입니다.

## 작은 변경 처리

변경 수가 작으면 block 단위 전략이 실용적입니다.

1. block 안에서 변경될 모든 간선을 질의를 미리 읽어 표시한다.
2. 표시한 간선을 전부 제외한 고정 활성 간선의 MSF를 만든다.
3. query마다 고정 MSF와 현재 활성인 변경 간선을 합쳐 Kruskal을 돌린다.

block마다 고정 MSF 구성 비용과 질의마다 O((N+B)log(N+B)) 비용을 함께 계산합니다.

block에서 가중치·활성 여부가 바뀌는 간선을 전부 먼저 제외하고 나머지 고정 활성 간선의 MSF를 만듭니다. 각 질의는 그 MSF와 현재 활성인 변경 간선을 합쳐 Kruskal을 돌립니다. 후보는 O(N+B)개라 큰 N에서 자동으로 빠른 방법은 아닙니다.

## 시간 복잡도 감각

| 접근 | 대략적인 비용 | 특징 |
| --- | ---: | --- |
| 매 query rebuild | `O(N + M log(M+1))` | 단순하고 안전 |
| 추가만 처리 | LCT 사용 시 상각 `O(log N)` 갱신 | 서로 다른 component면 link, 같으면 path max 교체 |
| block rebuild | `O((M log M) * blocks + small Kruskal)` | 변경 수가 작을 때 |
| full online dynamic MST | 고급 자료구조 필요 | 구현 위험 큼 |

문제 제한이 아주 크지 않다면 먼저 baseline으로 correctness를 잡고, 병목이 확인되면 block/offline으로 줄입니다.