# DSU có trọng số

**Người viết:**
> **Nguyễn Tường Duy - VNU University of Engineering and Technology**

## Giới thiệu

Chúng ta sẽ giải bài toán tìm cây khung nhỏ nhất với truy vấn thêm cạnh online sử dụng cấu trúc dữ liệu có tên là **DSU có trọng số**. Mặc dù bài toán này có thể giải bằng cấu trúc dữ liệu Link-Cut Tree nhưng Link-Cut Tree khó code và có hằng số lớn hơn. Cấu trúc dữ liệu mà mình sẽ giới thiệu với các bạn có hằng số vô cùng nhỏ vì nó chỉ làm những thao tác trên mảng, nhanh hơn Link-Cut Tree khoảng *3* - *6* lần.

## Bài toán ban đầu

### [CSES - New Roads Queries](https://cses.fi/problemset/task/2101)

#### - Tóm tắt đề bài:

Cho một đồ thị vô hướng *n* đỉnh, *m* cạnh, cạnh thứ *i* có thời gian thêm vào là *i*. Trả lời *q* truy vấn: tìm thời gian nhỏ nhất để từ *a* có thể đi tới *b* (in *-1* nếu từ *a* không bao giờ đi tới *b*).

#### - Giới hạn:

* $1 \leq n, m, q \leq 2 \cdot 10^5$
* $1 \leq a, b \leq n$

#### - Lời giải:

Bài toán này có thể giải quyết bằng nhiều cách khác nhau, mình sẽ trình bày lời giải sử dụng DSU: Chúng ta sẽ sử dụng DSU nhưng không có kĩ thuật nén đường đi và thêm cạnh theo thứ tự thời gian tăng dần. Ngoài ra chúng ta sẽ lưu thời gian của cạnh thêm vào. Cụ thể chúng ta sẽ dùng *3* mảng: *parent*, *weight*, *size*. Khi nối *u* và *v* chúng ta cập nhật *parent[v] = u*, *weight[v] = w*, *size[u] += size[v]*. Bây giờ chúng ta có thể tìm được đại diện của tập hợp chứa *u* tại thời điểm *w*. Một cách giải bài toán là chặt nhị phân để tìm đáp án, độ phức tạp là $O(\log^2 n)$ mỗi truy vấn. Một cách khác nhanh hơn là tìm tổ tiên chung gần nhất của *u* và *v* trên cây DSU. Chúng ta sẽ di chuyển đỉnh có trọng số cạnh nhỏ nhất hiện tại lên trên cho tới khi hai đỉnh trùng nhau. Có thể thấy thuật toán trên đúng vì trọng số cạnh trong cây DSU tăng dần từ lá lên đến gốc. Độ phức tạp là $O(\log n)$ mỗi truy vấn.

::: spoiler Code (CSES - New Roads Queries)

#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> parent, weight, size;

    dsu(int n): parent(n + 1), weight(n + 1), size(n + 1) {
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
            weight[i] = INT_MAX;
            size[i] = 1;
        }
    }

    int find(int u) {
        if (parent[u] == u) return u;
        return find(parent[u]);
    }

    void merge(int u, int v, int w) {
        u = find(u);
        v = find(v);
        if (u != v) {
            if (size[u] < size[v]) swap(u, v);
            parent[v] = u;
            weight[v] = w;
            size[u] += size[v];
        }
    }

    bool connected(int u, int v) {
        return find(u) == find(v);
    }

    int query(int u, int v) {
        if (!connected(u, v)) return -1;
        int ans = 0;
        while (u != v) {
            if (weight[u] > weight[v]) swap(u, v);
            ans = max(ans, weight[u]);
            u = parent[u];
        }
        return ans;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;

    dsu D(n);

    for (int i = 1; i <= m; ++i) {
        int a, b;
        cin >> a >> b;
        D.merge(a, b, i);
    }

    for (int i = 1; i <= q; ++i) {
        int a, b;
        cin >> a >> b;
        cout << D.query(a, b) << "\n";
    }
}

:::

## Tìm cây khung nhỏ nhất với truy vấn thêm cạnh online

### [CSES - Road Reparation](https://cses.fi/problemset/task/1675)

#### - Tóm tắt đề bài:

Cho một đồ thị vô hướng *n* đỉnh, *m* cạnh, cạnh nối *a - b* có trọng số là *c*. Chọn một số cạnh sao cho giữa hai đỉnh bất kì luôn tồn tại đường đi chỉ gồm cách cạnh đã chọn và tổng trọng số các cạnh nhỏ nhất.

Đây là bài toán tìm cây khung nhỏ nhất cơ bản. Chúng ta sẽ cố gắng giải bài toán này mà không cần sắp xếp các cạnh theo trọng số tăng dần.

#### - Giới hạn:

* $1 \leq n \leq 10^5$
* $1 \leq m \leq 2 \cdot 10^5$
* $1 \leq a, b \leq n$
* $1 \leq c \leq 10^9$

#### - Lời giải:

Sử dụng ý tưởng của bài toán trên chúng ta có thuật toán gần đúng như sau: Chúng ta sẽ thêm cạnh nối *u - v* có trọng số là *w*. Gọi *U*, *V* là đại diện của *u*, *v* tại thời điểm *w*. Giả sử chúng ta nối *U - V* với *U* là cha *V*, điều này có nghĩa là chúng ta phải bỏ cạnh nối *V* đến cha của nó. Sau đó chúng ta sẽ thêm đệ quy cạnh vừa bỏ đi.

##### Thuật toán trên có *3* vấn đề:

###### 1. Trọng số cạnh trong cây DSU không còn tăng dần từ lá lên đến gốc.

Giải quyết vấn đề *1* khá đơn giản: Chúng ta chỉ cần "nhảy qua" những cạnh có trọng số nhỏ hơn cạnh hiện tại. Thao tác tìm cha của đỉnh *u* sẽ trông như thế này:

::: spoiler Code

int& parent(int u) {
    if (par[u] == u) return par[u];
    while (weight[par[u]] <= weight[u]) par[u] = par[par[u]];
    return par[u];
}

:::

###### 2. Kích cỡ thành phần liên thông thay đổi do phải xóa cạnh nên chúng ta không thể sử dụng kĩ thuật gộp theo kích cỡ.

Vấn đề *2* cũng có cách xử lí đơn giản: Thay vì gộp theo kích cỡ, chúng ta sẽ gộp theo độ ưu tiên. Cụ thể chúng ta sẽ gán cho mỗi đỉnh độ ưu tiên ngẫu nhiên. Khi thêm cạnh, đỉnh có độ ưu tiên lớn hơn sẽ là cha.

###### 3. Chúng ta sẽ làm gì nếu thêm cạnh nối *u - v* khi *u* và *v* đã được kết nối?

Vấn đề *3* có thế giải quyết bằng tính chất của cây khung nhỏ nhất. Do trọng số tăng dần từ lá lên gốc nên chúng ta có thể dùng thuật toán tìm tổ tiên chung gần nhất của bài toán ban đầu để tìm cạnh có trọng số lớn nhất thuộc đường đi đơn giản giữa *u* và *v*. Nếu trọng số của cạnh đó lớn hơn trọng số của cạnh thêm vào thì xóa cạnh đó đi và thực hiện thuật toán thêm cạnh như trên.

#### - Tổng kết

Kết hợp tất cả các điều trên chúng ta có cấu trúc dữ liệu như sau:

::: spoiler Code (CSES - Road Reparation)

#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> par, weight, priority;

    dsu(int n): par(n + 1), weight(n + 1), priority(n + 1) {
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
            weight[i] = INT_MAX;
            priority[i] = i;
        }
        uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(priority.begin() + 1, priority.end(), mt19937(seed));
    }

    int& parent(int u) {
        if (par[u] == u) return par[u];
        while (weight[par[u]] <= weight[u]) par[u] = par[par[u]];
        return par[u];
    }

    int find(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) u = parent(u);
        return u;
    }

    void add_edge(int u, int v, int w) {
        while (u != v) {
            u = find(u, w);
            v = find(v, w);
            if (priority[u] < priority[v]) swap(u, v);
            int temp_parent = parent(v), temp_weight = weight[v];
            parent(v) = u;
            weight[v] = w;
            u = temp_parent;
            w = temp_weight;
        }
    }

    int max_edge(int u, int v) {
        if (find(u) != find(v)) return -1;
        while (true) {
            if (weight[u] > weight[v]) swap(u, v);
            if (parent(u) == v) break;
            u = parent(u);
        }
        return u;
    }

    void delete_edge(int u) {
        parent(u) = u;
        weight[u] = INT_MAX;
    }

    int merge(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) {
            add_edge(u, v, w);
            return w;
        } else if (weight[p] > w) {
            int res = w - weight[p];
            delete_edge(p);
            add_edge(u, v, w);
            return res;
        }
        return 0;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    dsu D(n);
    long long ans = 0;

    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        ans += D.merge(a, b, c);
    }

    for (int i = 2; i <= n; ++i) {
        if (D.find(i) != D.find(i - 1)) {
            cout << "IMPOSSIBLE";
            return 0;
        }
    }

    cout << ans;
}

:::

Vì mỗi đỉnh có độ ưu tiên ngẫu nhiên nên chúng ta có thể coi cây DSU là cây ngẫu nhiên. Như vậy độ sâu của cây DSU sẽ khoảng $\log n$, suy ra cấu trúc dữ liệu trên có độ phức tạp $O(\log n)$ mỗi truy vấn.

## Một số thao tác khác

### - Xóa cạnh lớn nhất

Chúng ta có thể xóa cạnh lớn nhất vì trước đó không có đỉnh nào dùng nó để "nhảy lên".

### - Lưu kích thước của thành phần liên thông:

Chúng ta có thể làm việc này bằng cách tạo thêm một mảng *size* với *size[u]* là kích thước của cây con gốc *u*. Cách đơn giản nhất là thay đổi mảng *size* khi xóa cạnh và thêm cạnh.

::: spoiler Code

struct dsu {
    vector<int> par, weight, priority, size;

    dsu(int n): par(n + 1), weight(n + 1), priority(n + 1), size(n + 1) {
        for (int i = 1; i <= n; ++i) {
            par[i] = priority[i] = i;
            weight[i] = INT_MAX;
            size[i] = 1;
        }
        uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(priority.begin() + 1, priority.end(), mt19937(seed));
    }

    int& parent(int u) {
        if (par[u] == u) return par[u];
        while (weight[par[u]] <= weight[u]) {
            size[par[u]] -= size[u];
            par[u] = par[par[u]];
        }
        return par[u];
    }

    int find(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) u = parent(u);
        return u;
    }

    int get_size(int u) {
        return size[find(u)];
    }

    void disconnect(int u) {
        if (parent(u) != u) {
            disconnect(parent(u));
            size[parent(u)] -= size[u];
        }
    }

    int connect(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) {
            size[parent(u)] += size[u];
            u = parent(u);
        }
        return u;
    }

    void add_edge(int u, int v, int w) {
        disconnect(u);
        disconnect(v);
        while (u != v) {
            u = connect(u, w);
            v = connect(v, w);
            if (priority[u] < priority[v]) swap(u, v);
            int temp_parent = parent(v), temp_weight = weight[v];
            parent(v) = u;
            weight[v] = w;
            u = temp_parent;
            w = temp_weight;
        }
        connect(u);
    }

    int max_edge(int u, int v) {
        if (find(u) != find(v)) return -1;
        while (true) {
            if (weight[u] > weight[v]) swap(u, v);
            if (parent(u) == v) break;
            u = parent(u);
        }
        return u;
    }

    void delete_edge(int u) {
        int v = u;
        while (parent(v) != v) {
            v = parent(v);
            size[v] -= size[u];
        }
        parent(u) = u;
        weight[u] = INT_MAX;
    }

    void merge(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) {
            add_edge(u, v, w);
        } else if (weight[p] > w) {
            delete_edge(p);
            add_edge(u, v, w);
        }
    }
};

:::

### - Có bao nhiêu đỉnh có thể đi tới từ đỉnh *u* bằng các cạnh có trọng số $\leq$ *w*?

Để trả lời truy vấn này chúng ta đi tới đỉnh đại diện cho *u* tại thời điểm *w* và tính tổng kích thước của tất cả con trực tiếp có trọng số cạnh $\leq$ *w*. Chúng ta sử dụng cấu trúc dữ liệu treap lưu con trực tiếp ở mỗi đỉnh, khi tính kết quả thì tách treap thành hai phần $\leq$ *w*, > *w* và tính tổng của phần $\leq$ *w*. Thuật toán này có độ phức tạp $O(\log^2 n)$ mỗi truy vấn.

## Bài toán Dynamic Connectivity

### [CSES - Dynamic Connectivity](https://cses.fi/problemset/task/2133/)

#### - Tóm tắt đề bài:

Cho một đồ thị có hướng *n* đỉnh, *m* cạnh. Có *k* truy vấn là thêm hoặc xóa cạnh *a - b*. Tìm số thành phần liên thông sau mỗi truy vấn.

#### - Giới hạn:

* $2 \leq n \leq 10^5$
* $1 \leq m, k \leq 10^5$
* $1 \leq a, b \leq n$

#### - Lời giải:

Chúng ta gán trọng số cho cạnh là thời gian cạnh đó bị xóa (nếu không bao giờ bị xóa thì trọng số là *INF*). Khi đó truy vấn xóa cạnh trở thành truy vấn xóa cạnh trọng số nhỏ nhất của đồ thị (tương tự xóa cạnh trọng số lớn nhất). Chúng ta xử lí truy vấn trong thời gian $O(\log n)$ bằng cấu trúc dữ liệu DSU có trọng số.

::: spoiler Code (CSES - Dynamic Connectivity)

#include "bits/stdc++.h"
using namespace std;

struct dsu {
    int component;
    vector<int> par, weight, priority;

    dsu(int n): component(n), par(n + 1), weight(n + 1), priority(n + 1) {
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
            weight[i] = INT_MAX;
            priority[i] = i;
        }
        uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(priority.begin() + 1, priority.end(), mt19937(seed));
    }

    int& parent(int u) {
        if (par[u] == u) return par[u];
        while (weight[par[u]] <= weight[u]) par[u] = par[par[u]];
        return par[u];
    }

    int find(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) u = parent(u);
        return u;
    }

    void add_edge(int u, int v, int w) {
        --component;
        while (u != v) {
            u = find(u, w);
            v = find(v, w);
            if (priority[u] < priority[v]) swap(u, v);
            int temp_parent = parent(v), temp_weight = weight[v];
            parent(v) = u;
            weight[v] = w;
            u = temp_parent;
            w = temp_weight;
        }
    }

    int max_edge(int u, int v) {
        if (find(u) != find(v)) return -1;
        while (true) {
            if (weight[u] > weight[v]) swap(u, v);
            if (parent(u) == v) break;
            u = parent(u);
        }
        return u;
    }

    void delete_edge(int u) {
        ++component;
        parent(u) = u;
        weight[u] = INT_MAX;
    }

    void merge(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) {
            add_edge(u, v, w);
        } else if (weight[p] > w) {
            delete_edge(p);
            add_edge(u, v, w);
        }
    }

    void del(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p != -1 && weight[p] == w) delete_edge(p);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    vector<pair<int, int>> query(m + k);

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        query[i] = make_pair(a, b);
    }

    for (int i = 0; i < k; ++i) {
        int t, a, b;
        cin >> t >> a >> b;
        if (a > b) swap(a, b);
        query[i + m] = make_pair(a, b);
    }

    vector<int> weight(m + k, m + k);
    vector<bool> add(m + k, 0);
    map<pair<int, int>, int> mp;

    for (int i = 0; i < m + k; ++i) {
        if (mp.find(query[i]) == mp.end()) {
            add[i] = 1;
            mp[query[i]] = i;
        } else {
            weight[mp[query[i]]] = i;
            weight[i] = i;
            mp.erase(query[i]);
        }
    }

    dsu D(n);

    for (int i = 0; i < m + k; ++i) {
        if (add[i]) D.merge(query[i].first, query[i].second, -weight[i]);
        else D.del(query[i].first, query[i].second, -weight[i]);
        if (i >= m - 1) cout << D.component << " ";
    }
}

:::

## Bài toán Dynamic Minimum Spanning Tree

### [Codeforces - It's Time to Repair the Roads](https://codeforces.com/problemsets/acmsguru/problem/99999/529)

#### - Tóm tắt đề bài:

Cho một đồ thị vô hướng *n* đỉnh, *m* cạnh, cạnh nối *x - y* có trọng số là *p*. Có *t* truy vấn thay đổi trọng số cạnh thứ *e* thành *c*. Tìm cây khung nhỏ nhất sau mỗi truy vấn.

#### - Giới hạn:

* $2 \leq n \leq 4 \cdot 10^4$
* $n - 1 \leq m \leq 4 \cdot 10^4$
* $1 \leq x, y \leq n, x \neq y$
* $1 \leq p \leq 4 \cdot 10^4$
* $1 \leq t \leq 4 \cdot 10^4$
* $1 \leq e \leq m$
* $1 \leq c \leq 4 \cdot 10^4$

#### - Lời giải:

Coi *t* truy vấn là *t* thời điểm, khi đó truy vấn thay đổi trọng số của cạnh có thể chuyển thành truy vấn thêm cạnh từ thời điểm *L* đến *R*. Chúng ta dùng cấu trúc dữ liệu *Cây Phân Đoạn* để xử lí truy vấn hiệu quả. Sau đó chúng ta DFS Cây Phân Đoạn bắt đầu từ gốc. Trong quá trình duyệt, chúng ta sẽ tính cây khung nhỏ nhất bằng cấu trúc dữ liệu DSU có trọng số. Khi truy cập một đỉnh trong Cây Phân Đoạn, chúng ta sẽ thêm các cạnh được lưu trong đỉnh đó. Khi thoát khỏi một đỉnh, chúng ta có thể xóa các cạnh đã thêm trước đó bằng cách dùng stack để lưu các phần tử đã thay đổi. Như vậy ta được thuật toán có độ phức tạp là $O(t\log t\log n)$.

::: spoiler Code (Codeforces - It's Time to Repair the Roads)

#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> par, weight, priority;
    vector<pair<int&, int>> history;

    dsu(int n): par(n + 1), weight(n + 1), priority(n + 1) {
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
            weight[i] = INT_MAX;
            priority[i] = i;
        }
        uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(priority.begin() + 1, priority.end(), mt19937(seed));
    }

    void set(int &p, int v) {
        history.emplace_back(p, p);
        p = v;
    }

    int& parent(int u) {
        if (par[u] == u) return par[u];
        while (weight[par[u]] <= weight[u]) set(par[u], par[par[u]]);
        return par[u];
    }

    int find(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) u = parent(u);
        return u;
    }

    void add_edge(int u, int v, int w) {
        while (u != v) {
            u = find(u, w);
            v = find(v, w);
            if (priority[u] < priority[v]) swap(u, v);
            int temp_parent = parent(v), temp_weight = weight[v];
            set(parent(v), u);
            set(weight[v], w);
            u = temp_parent;
            w = temp_weight;
        }
    }

    int max_edge(int u, int v) {
        if (find(u) != find(v)) return -1;
        while (true) {
            if (weight[u] > weight[v]) swap(u, v);
            if (parent(u) == v) break;
            u = parent(u);
        }
        return u;
    }

    void delete_edge(int u) {
        set(parent(u), u);
        set(weight[u], INT_MAX);
    }

    int merge(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) {
            add_edge(u, v, w);
            return w;
        } else if (weight[p] > w) {
            int res = w - weight[p];
            delete_edge(p);
            add_edge(u, v, w);
            return res;
        }
        return 0;
    }

    int snapshot() {
        return history.size();
    }
 
    void rollback(int x) {
        while (history.size() > x) {
            history.back().first = history.back().second;
            history.pop_back();
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edge(m);
    for (auto &[x, y, p]: edge) cin >> x >> y >> p;

    int t;
    cin >> t;

    vector<vector<tuple<int, int, int>>> tr(t << 2);

    function<void(int, int, tuple<int, int, int>, int, int, int)> add = [&] (int u, int v, tuple<int, int, int> x, int id, int l, int r) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            tr[id].emplace_back(x);
            return;
        }
        int mid = (l + r) >> 1;
        add(u, v, x, id << 1, l, mid);
        add(u, v, x, id << 1 | 1, mid + 1, r);
    };

    vector<int> lst(m, 0);

    for (int e, c, i = 0; i < t; ++i) {
        cin >> e >> c;
        --e;
        add(lst[e], i - 1, edge[e], 1, 0, t - 1);
        get<2>(edge[e]) = c;
        lst[e] = i;
    }

    for (int i = 0; i < m; ++i) add(lst[i], t - 1, edge[i], 1, 0, t - 1);

    dsu D(n);

    function<void(int, int, int, int)> dnc = [&] (int res, int id, int l, int r) {
        int tmp = D.snapshot();
        for (auto &[u, v, w]: tr[id]) res += D.merge(u, v, w);
        if (l == r) cout << res << "\n";
        else {
            int mid = (l + r) >> 1;
            dnc(res, id << 1, l, mid);
            dnc(res, id << 1 | 1, mid + 1, r);
        }
        D.rollback(tmp);
    };

    dnc(0, 1, 0, t - 1);
}

:::

## Bài tập ví dụ

### [Codeforces - Edges in MST](https://codeforces.com/problemset/problem/160/D)

#### - Tóm tắt đề bài:

Cho một đồ thị vô hướng, liên thông *n* đỉnh, *m* cạnh, cạnh nối *a - b* có trọng số là *w*. Trả lời câu hỏi sau cho mỗi cạnh của đồ thị: Xác định cạnh đó thuộc tất cả các cây khung nhỏ nhất, hay thuộc ít nhất một cây khung nhỏ nhất, hay không thuộc cây khung nhỏ nhất nào.

#### - Giới hạn:

* $2 \leq n \leq 10^5$
* $n - 1 \leq m \leq min(10^5, \frac{n(n-1)}{2})$
* $1 \leq a, b \leq n$
* $1 \leq w \leq 10^6$

#### - Lời giải:

Chúng ta có ý tưởng giải bài toán như sau: Xét cạnh thứ *i* là cạnh nối *u - v* có trọng số là *w*, dựng cây khung nhỏ nhất của *m - 1* cạnh còn lại. Nếu *u* và *v* không thuộc cùng thành phần liên thông thì cạnh đó thuộc tất cả các cây khung nhỏ nhất. Nếu *u* và *v* thuộc cùng thành phần liên thông thì gọi trọng số cạnh lớn nhất trên đường đi giữa *u* và *v* là *x*, khi thêm cạnh thứ *i* vào xảy ra *3* trường hợp:

* $w > x$: cạnh không thuộc cây khung nhỏ nhất nào.
* $w = x$: cạnh thuộc ít nhất một cây khung nhỏ nhất.
* $w < x$: cạnh thuộc tất cả các cây khung nhỏ nhất.

Ý tưởng trên cho chúng ta thuật toán có độ phức tạp là $O(m^2)$. Để tối ưu thuật toán, chúng ta sử dụng cách làm tương tự như bài toán Dynamic Minimum Spanning Tree. Khi trả lời câu hỏi với cạnh thứ *i*, chúng ta sẽ xóa cạnh thứ *i*, tìm kết quả, sau đó thêm lại cạnh thứ *i*. Như vậy chúng ta được thuật toán có độ phức tạp là $O(m \log m \log n)$.

::: spoiler Code (Codeforces - Edges in MST)

#include "bits/stdc++.h"
using namespace std;

struct dsu {
    vector<int> par, weight, priority;
    vector<pair<int&, int>> history;

    dsu(int n): par(n + 1), weight(n + 1), priority(n + 1) {
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
            weight[i] = INT_MAX;
            priority[i] = i;
        }
        uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(priority.begin() + 1, priority.end(), mt19937(seed));
    }

    void set(int &p, int v) {
        history.emplace_back(p, p);
        p = v;
    }

    int& parent(int u) {
        if (par[u] == u) return par[u];
        while (weight[par[u]] <= weight[u]) set(par[u], par[par[u]]);
        return par[u];
    }

    int find(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) u = parent(u);
        return u;
    }

    void add_edge(int u, int v, int w) {
        while (u != v) {
            u = find(u, w);
            v = find(v, w);
            if (priority[u] < priority[v]) swap(u, v);
            int temp_parent = parent(v), temp_weight = weight[v];
            set(parent(v), u);
            set(weight[v], w);
            u = temp_parent;
            w = temp_weight;
        }
    }

    int max_edge(int u, int v) {
        if (find(u) != find(v)) return -1;
        while (true) {
            if (weight[u] > weight[v]) swap(u, v);
            if (parent(u) == v) break;
            u = parent(u);
        }
        return u;
    }

    void delete_edge(int u) {
        set(parent(u), u);
        set(weight[u], INT_MAX);
    }

    void merge(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) {
            add_edge(u, v, w);
        } else if (weight[p] > w) {
            delete_edge(p);
            add_edge(u, v, w);
        }
    }

    int snapshot() {
        return history.size();
    }
 
    void rollback(int x) {
        while (history.size() > x) {
            history.back().first = history.back().second;
            history.pop_back();
        }
    }

    int query(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) return 1;
        if (w > weight[p]) return -1;
        return w < weight[p];
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edge(m);
    for (auto &[a, b, w]: edge) cin >> a >> b >> w;

    vector<vector<tuple<int, int, int>>> tr(m << 2);

    function<void(int, int, tuple<int, int, int>, int, int, int)> add = [&] (int u, int v, tuple<int, int, int> x, int id, int l, int r) {
        if (v < l || r < u) return;
        if (u <= l && r <= v) {
            tr[id].emplace_back(x);
            return;
        }
        int mid = (l + r) >> 1;
        add(u, v, x, id << 1, l, mid);
        add(u, v, x, id << 1 | 1, mid + 1, r);
    };

    for (int i = 0; i < m; ++i) {
        add(0, i - 1, edge[i], 1, 0, m - 1);
        add(i + 1, m - 1, edge[i], 1, 0, m - 1);
    }

    dsu D(n);

    function<void(int, int, int)> dnc = [&] (int id, int l, int r) {
        int tmp = D.snapshot();
        for (auto &[u, v, w]: tr[id]) D.merge(u, v, w);
        if (l == r) {
            auto &[a, b, w] = edge[l];
            int res = D.query(a, b, w);
            if (res == -1) cout << "none\n";
            else if (res) cout << "any\n";
            else cout << "at least one\n";
        } else {
            int mid = (l + r) >> 1;
            dnc(id << 1, l, mid);
            dnc(id << 1 | 1, mid + 1, r);
        }
        D.rollback(tmp);
    };

    dnc(1, 0, m - 1);
}

:::

### [Codeforces - Pastoral Oddities](https://codeforces.com/contest/603/problem/E)

#### - Tóm tắt đề bài:

Cho một đồ thị vô hướng *n* đỉnh, *m* cạnh, cạnh nối *a - b* có trọng số là *l*. Cạnh thứ *i* có thời gian thêm vào là *i*. Với mỗi thời điểm *i* từ *1* đến *m*, trả lời truy vấn: Chọn một số cạnh thỏa mãn mỗi đỉnh kề với một số lẻ các cạnh và trọng số của cạnh lớn nhất là nhỏ nhất. In ra trọng số của cạnh lớn nhất.

#### - Giới hạn:

* $2 \leq n \leq 10^5$
* $1 \leq m \leq 3 \cdot 10^5$
* $1 \leq a, b \leq n, a \neq b$
* $1 \leq l \leq 10^9$

#### - Lời giải:

Xét một đồ thị liên thông bất kì, gọi *G* là tên của đồ thị, *V* là tập hợp đỉnh, *E* là tập hợp cạnh.

Theo [bổ đề bắt tay](https://en.wikipedia.org/wiki/Handshaking_lemma), chúng ta có $\sum_{u \in V} \deg(u) = 2|E|$. Như vậy chúng ta được tính chất sau: $\sum_{u \in V} \deg(u)$ là số chẵn. Chúng ta sẽ sử dụng tính chất trên để chứng minh trên đồ thị *G*, hai điều sau tương đương:
* |V| là số chẵn.
* Luôn chọn được một tập hợp cạnh là tập hợp con của *E* thỏa mãn mỗi đỉnh kề với một số lẻ các cạnh hay bậc của mỗi đỉnh là số lẻ.

Nếu |V| chẵn: Xét một cây khung bất kì của *G*. Chúng ta có thuật toán như sau: Chọn một đỉnh bất kì là gốc của cây. Chúng ta sẽ BFS với các đỉnh nguồn là các đỉnh lá của cây. Xét một đỉnh không phải gốc, khi đó chúng ta chỉ có thể đi từ đỉnh đang thăm đến đúng một đỉnh chưa thăm là đỉnh cha của nó. Như vậy chúng ta sẽ thêm cạnh nối đỉnh đang thăm với đỉnh cha của nó khi bậc của đỉnh đang thăm là số chẵn, không thì không thêm cạnh nào. Thuật toán trên chỉ sai khi chúng ta thăm đến đỉnh gốc và đỉnh gốc có bậc là số chẵn, khi đó *n - 1* đỉnh còn lại đều có bậc là số lẻ, suy ra $\sum_{u \in V} \deg(u)$ là số lẻ (mâu thuẫn). Tóm lại thuật toán trên luôn tìm được một tập hợp cạnh là tập hợp con của *E* thỏa mãn bậc của mỗi đỉnh là số lẻ.

Nếu tồn tại tập hợp cạnh thỏa mãn: Giả sử |V| lẻ, khi đó $\sum_{u \in V} \deg(u)$ là số lẻ (mâu thuẫn). Vậy |V| phải là số chẵn.

Như vậy trên một đồ thị bất kì, thay vì chọn một số cạnh thỏa mãn bậc của mỗi đỉnh là số lẻ thì chúng ta chỉ cần chọn một số thành phần liên thông có số đỉnh là số chẵn. Và để trọng số của cạnh lớn nhất là nhỏ nhất thì chúng ta tìm cây khung nhỏ nhất của mỗi thành phần liên thông. Qua đó chúng ta có thuật toán tham lam như sau: Để trả lời truy vấn sau khi thêm cạnh thứ *i*, chúng ta duyệt các cạnh từ *1* đến *i* theo thứ tự trọng số tăng dần. Chúng ta sẽ thêm cạnh nối *u - v* khi *u* và *v* không thuộc cùng một thành phần liên thông và kích thước thành phần liên thông của *u* và *v* là số lẻ, để kiểm tra những điều trên thì chúng ta dùng cấu trúc dữ liệu DSU. Chúng ta không chọn được một số cạnh thỏa mãn khi vẫn tồn tại thành phần liên thông có kích thước là số lẻ, không thì kết quả của truy vấn là trọng số cạnh thêm vào cuối cùng. Qua đó chúng ta được thuật toán có độ phức tạp $O(m^2)$, không thể chạy dưới giới hạn thời gian của bài toán.

Vấn đề của thuật toán trên là chúng ta phải tìm lại cây khung nhỏ nhất sau mỗi lần thêm cạnh. Để khắc phục điều trên thì chúng ta dùng cấu trúc dữ liệu DSU có trọng số. Nhưng còn một vấn đề nữa là chúng ta chỉ thêm cạnh nối *u - v* khi kích thước thành phần liên thông của *u* và *v* là số lẻ. Nếu tồn tại thành phần liên thông có kích thước là số lẻ thì không có kết quả nên chúng ta chỉ xét trường hợp tất cả thành phần liên thông đều có kích thước là số chẵn. Chúng ta giải quyết vấn đề này bằng cách xóa cạnh nối *u - v* nếu sau khi xóa kích thước thành phần liên thông của *u* và *v* là số chẵn. Cụ thể hơn, chúng ta dùng cấu trúc dữ liệu hàng đợi ưu tiên để lưu các cạnh đã thêm vào theo thứ tự trọng số giảm dần. Sau khi thêm cạnh vào cấu trúc dữ liệu DSU có trọng số, chúng ta sẽ xóa cạnh đầu trong hàng đợi ưu tiên cho đến khi không xóa được nữa, khi đó trọng số của cạnh không xóa được là kết quả truy vấn. Thao tác xóa cạnh có thể thực hiện được vì cạnh chúng ta xóa là cạnh có trọng số lớn nhất. Tóm lại chúng ta được thuật toán cuối cùng có độ phức tạp $O(m \log m)$.

::: spoiler Code (Codeforces - Pastoral Oddities)

#include "bits/stdc++.h"
using namespace std;

struct dsu {
    int odd;
    vector<int> par, weight, priority, size;

    dsu(int n): odd(n), par(n + 1), weight(n + 1), priority(n + 1), size(n + 1) {
        for (int i = 1; i <= n; ++i) {
            par[i] = priority[i] = i;
            weight[i] = INT_MAX;
            size[i] = 1;
        }
        uint64_t seed = chrono::high_resolution_clock::now().time_since_epoch().count();
        shuffle(priority.begin() + 1, priority.end(), mt19937(seed));
    }

    int& parent(int u) {
        if (par[u] == u) return par[u];
        while (weight[par[u]] <= weight[u]) {
            size[par[u]] -= size[u];
            par[u] = par[par[u]];
        }
        return par[u];
    }

    int find(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) u = parent(u);
        return u;
    }

    int get_size(int u) {
        return size[find(u)];
    }

    void disconnect(int u) {
        if (parent(u) != u) {
            disconnect(parent(u));
            size[parent(u)] -= size[u];
        }
    }

    int connect(int u, int w = INT_MAX - 1) {
        while (weight[u] <= w) {
            size[parent(u)] += size[u];
            u = parent(u);
        }
        return u;
    }

    void add_edge(int u, int v, int w) {
        disconnect(u);
        disconnect(v);
        while (u != v) {
            u = connect(u, w);
            v = connect(v, w);
            if (priority[u] < priority[v]) swap(u, v);
            int temp_parent = parent(v), temp_weight = weight[v];
            parent(v) = u;
            weight[v] = w;
            u = temp_parent;
            w = temp_weight;
        }
        connect(u);
    }

    int max_edge(int u, int v) {
        if (find(u) != find(v)) return -1;
        while (true) {
            if (weight[u] > weight[v]) swap(u, v);
            if (parent(u) == v) break;
            u = parent(u);
        }
        return u;
    }

    void delete_edge(int u) {
        int v = u;
        while (parent(v) != v) {
            v = parent(v);
            size[v] -= size[u];
        }
        parent(u) = u;
        weight[u] = INT_MAX;
    }

    void merge(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p == -1) {
            if (get_size(u) % 2 && get_size(v) % 2) odd -= 2;
            add_edge(u, v, w);
        } else if (weight[p] > w) {
            delete_edge(p);
            add_edge(u, v, w);
        }
    }

    bool del(int u, int v, int w) {
        int p = max_edge(u, v);
        if (p != -1 && weight[p] == w) {
            delete_edge(p);
            if (get_size(u) % 2 && get_size(v) % 2) {
                odd += 2;
                merge(u, v, w);
                return false;
            }
        }
        return true;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> e(m);
    for (auto &[a, b, l]: e) cin >> a >> b >> l;

    priority_queue<tuple<int, int, int>> q;
    dsu D(n);

    for (auto &[a, b, l]: e) {
        D.merge(a, b, l);
        q.push(make_tuple(l, a, b));
        if (D.odd == 0) {
            while (true) {
                auto [l, a, b] = q.top();
                if (!D.del(a, b, l)) {
                    cout << l << "\n";
                    break;
                }
                q.pop();
            }
        } else {
            cout << "-1\n";
        }
    }
}

:::

## Tham khảo

[Maintaining mst with online edge insertions — no LCT needed](https://codeforces.com/blog/entry/130107)

## Bài tập

[Codeforces - Virus](https://codeforces.com/contest/1423/problem/H)

[BOI 2020 - Joker](https://codeforces.com/contest/1386/problem/C)

[Codeforces - Gift](https://codeforces.com/contest/76/problem/A)

[Codeforces - Minimum spanning tree for each edge](https://codeforces.com/contest/609/problem/E)

[DMOJ - CCO Preparation Test 4 P3 - Dynamic MST
](https://dmoj.ca/problem/ccoprep4p3)

[DMOJ - Wesley's Anger Contest 4 Problem 7 - Squirrel Cities
](https://dmoj.ca/problem/wac4p7)

[Library Checker - Dynamic Graph Vertex Add Component Sum](https://judge.yosupo.jp/problem/dynamic_graph_vertex_add_component_sum)