# Coding Challenge #2

## Đề Bài

:::spoiler [Đề bài gốc](https://oj.vnoi.info/problem/coding_challenge_dauthau) có thể được đọc trên hệ thống [VNOJ](https://oj.vnoi.info/contest/coding_challenge_2)
# **Coding Challenge #2 - Đấu Thầu**

Nước VNOI gồm $n$ thành phố và đang có kế hoạch liên kết chúng bằng $m$ con đường cao tốc *hai chiều*. Các con đường được đánh số từ 1 tới $m$, con đường thứ $i$ liên kết thành phố $u_i$ với $v_i$, và có *lợi nhuận* là $w_i$ (các giá trị $w_i$ phân biệt). Các con đường được thiết kế để tất cả các cặp thành phố đều có thể trực tiếp hoặc gián tiếp đi tới nhau.

Để xây dựng các con đường đó, chính quyền VNOI quyết định giao việc này cho $k$ nhà thầu. Sau những vòng bỏ phiếu căng thẳng, các nhà thầu này được xếp ở các vị trí từ $1$ tới $k$ thể hiện sự ưu tiên trong việc chọn tuyến đường thi công.

Mỗi nhà thầu sẽ được chọn một tập hợp các con đường trong $m$ đường cao tốc có sẵn trong kế hoạch, sao cho chúng *không tạo ra bất kì chu trình nào* và con đường không bị nhà thầu nào trước đó chọn. Giả sử, nếu nhà thầu chọn con đường $\{1 \to 2; 2 \to 3; 3 \to 1; 4 \to 5\}$ là không thoả mãn, bởi vì có chu trình $1 \to 2 \to 3 \to 1$. Lưu ý rằng ở ví dụ trên mũi tên được đánh hướng cho mục đích biểu diễn, còn trên thực tế thì các con đường là hai chiều.

Đầu tiên, nhà thầu thứ $1$ sẽ được chọn trước, sau đó tới nhà thầu thứ $2$, ... tới nhà thầu thứ $k$. Tất nhiên với cách này, một số con đường sẽ không được xây dựng, nhưng ở giai đoạn đầu của dự án thì đây là chuyện bình thường.

Tất nhiên, mỗi nhà thầu đều muốn tối đa hoá lợi ích của mình, vậy nên khi được chọn các con đường, họ sẽ chọn tập con đường mang tới **tổng lợi nhuận** lớn nhất có thể.

Nhiệm vụ của bạn là tính toán trước cho chính quyền VNOI xem mỗi nhà thầu từ $1$ tới $k$ sẽ có lợi nhuận là bao nhiêu khi tất cả đều chọn tập con đường một cách tối ưu.

## Input

- Dòng đầu tiên gồm 3 số nguyên $n, m, k$ miêu tả số thành phố, số con đường cần xây dựng và số nhà thầu;
- $m$ dòng tiếp theo, dòng thứ $i$ gồm $3$ số nguyên $u_i, v_i, w_i$ miêu tả con đường thứ $i$ trong kế hoạch, kết nối thành phố $u_i$ với $v_i$

## Output

- Gồm $k$ dòng, dòng thứ $i$ chứa giá trị là tổng lợi nhuận của nhà thầu thứ $i$ trong cách chia tối ưu.

## Subtask

- Trong tất cả các test $w_i \le 10^9$
- Có $20$% test tương ứng $20$% số điểm có $n \le 10^5, m \le 5 \times 10^5; k = 1$.
- Có $25$% test tương ứng $25$% số điểm có $n \le 10^3, m \le 10^4; k \le 1000$.
- Có $35$% test tương ứng $35$% số điểm có $n \le 10^3, m \le 5 \times 10^5; k \le 10^4$.
- $20$% số test còn lại tương ứng với $20$ số điểm có $n \le 10^5, m \le 5 \times 10^5; k \le 10^4$.

## Sample

### Sample 1

#### Input

4 5 1
1 2 5	
2 3 4	
3 4 3	
4 1 2	
1 3 1

#### Output

12

### Sample 2

#### Input

5 8 3
1 2 9
2 3 8
3 4 7
2 5 4
1 3 3
2 4 2
4 5 6
1 5 5

#### Output

30
14
0

:::

### Tóm Tắt Đề Bài

- Cho một đồ thị vô hướng liên thông $G = (V, E)$ có $n$ đỉnh và $m$ cạnh mang trọng số dương.
- Thực hiện thao tác sau $k$ lần:
- Tìm tập cạnh $E' \subseteq E$ sao cho:
- $E'$ không chứa chu trình;
- $E'$ có tổng trọng số lớn nhất có thể.
- Xóa các cạnh trong $E'$ khỏi $E$ ($E \leftarrow E \setminus E'$).
- Cho biết tổng trọng số của $E'$ sau mỗi lần thực hiện thao tác.

| Subtask | Điểm | Giới hạn |
| :--- | :--- | :--- |
| $1$ | $20$% | $n \le 10^5, m \le 5 \times 10^5; k = 1$ |
| $2$ | $25$% | $n \le 10^3, m \le 10^4; k \le 1000$ |
| $3$ | $35$% | $n \le 10^3, m \le 5 \times 10^5; k \le 10^4$ |
| $4$ | $20$% | $n \le 10^5, m \le 5 \times 10^5; k \le 10^4$ |

### Minh Họa Sample

:::spoiler Sample 1

- Minh hoạ đồ thị sau mỗi lần thực hiện thao tác


- Minh họa tập cạnh được chọn bởi các thao tác


:::

:::spoiler Sample 2

- Minh họa đồ thị sau mỗi lần thực hiện thao tác


- Minh họa tập cạnh được chọn bởi các thao tác

:::

## Lời Giải

### [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1)

**Giới hạn:** $n \le 10^5, m \le 5 \times 10^5; k = 1$

#### Ý Tưởng

- Vì số thao tác cần phải thực hiện $k$ là $1$, bài toán có thể được quy về tìm cây khung lớn nhất (ngược với [bài toán tìm cây khung nhỏ nhất](https://wiki.vnoi.info/algo/graph-theory/minimum-spanning-tree.md)) trong đồ thị đã cho bởi:
- Vì tập cạnh được chọn, tạm gọi là $E'$, không được chứa chu trình, $E'$ phải là một [rừng](https://en.wikipedia.org/wiki/Tree_(graph_theory)).
- Hơn nữa, vì đồ thị ban đầu liên thông, để tổng trọng số là lớn nhất, $E'$ phải là một cây khung (rừng liên thông gồm $n - 1$ cạnh).
Nếu $E'$ không liên thông, ta có thể thêm một cạnh mới mà không tạo ra chu trình, làm tăng tổng trọng số. Điều này mâu thuẫn với giả thiết tối ưu.
- Để tìm cây khung lớn nhất, ta có thể sử dụng [thuật toán Kruskal](https://cp-algorithms.com/graph/mst_kruskal.html) với một thay đổi nhỏ: Thay vì sắp xếp các cạnh theo thứ tự tăng dần trọng số, ta sắp xếp giảm dần.

:::spoiler Chứng minh
##### Cách chứng minh thứ nhất (ngắn gọn)

- Bài toán tìm cây khung lớn nhất trên đồ thị $G = (V, E)$ có thể được quy về bài toán tìm cây khung nhỏ nhất trên đồ thị $G' = (V, E)$ với cùng tập đỉnh và cạnh, nhưng với trọng số mới được đảo dấu ($w'_e = -w_e$ cho mọi cạnh $e \in E$).
Khi đó, cây khung nhỏ nhất của $G'$ cũng chính là cây khung lớn nhất của $G$.
- [Thuật toán Kruskal](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) có thể được dùng để tìm cây khung nhỏ nhất với các cạnh được duyệt theo thứ tự trọng số tăng dần. Khi áp dụng thuật toán trên đồ thị $G'$, thứ tự này tương đương với việc duyệt các cạnh của $G$ theo thứ tự trọng số giảm dần.

##### Cách chứng minh thứ hai (chi tiết)

>[!Note] Lưu ý:
>Cách chứng minh này phần lớn giống với cách minh tính đúng đắn của [thuật toán Kruskal](https://cp-algorithms.com/graph/mst_kruskal.html).

- Ta có thể chứng minh tính đúng đắn của ý tưởng trên bằng cách chứng minh quy nạp theo số lượng cạnh đã chọn với mệnh đề sau: *"Với tập cạnh $M$ được chọn bởi thuật toán tại mọi thời điểm, đồ thị luôn chứa một cây khung lớn nhất với tập cạnh $T$ chứa mọi cạnh của $M$"*.
- **Trường hợp cơ sở**: Mệnh đề trên hiển nhiên đúng với trường hợp ban đầu, khi $M$ không chứa bất kì cạnh nào bởi tập rỗng luôn là tập con của bất kì cây khung lớn nhất nào.
- **Bước quy nạp:** Khi ta xem xét có nên thêm cạnh $e$ vào $M$ đang thỏa mệnh đề trên không, ta có ba trường hợp sau:
1. $M \cup \{e\}$ chứa chu trình (thêm cạnh $e$ vào $M$ tạo nên một chu trình): Thuật toán sẽ không thêm $e$ vào $M$. Vì vậy, mệnh đề sẽ vẫn thỏa bởi $T$ cũng không thể chứa $e$ ($T$ là một cây khung nên không chứa chu trình).
2. $T$ chứa $e$: Mệnh đề trên tiếp tục thỏa.
3. $T$ không chứa $e$: Khi thêm cạnh $e$ vào $T$, ta có $T \cup {e}$ chứa một chu trình duy nhất có chứa cạnh $e$. Chu trình này phải chứa ít nhất một cạnh $f$ không ở trong $M$. Nếu không, việc thêm $e$ vào $M$ đã tạo chu trình, tức rơi vào trường hợp đầu tiên.
Vì cạnh $f$ đã không được chọn bởi thuật toán trước đó, trọng số của cạnh $f$ không thể lớn hơn trọng số cạnh $e$ ($w_f \leq w_e$). Khi này, ta nhận thấy rằng cây khung với tập cạnh $T' = T \cup \{e\} \setminus \{f\}$ cũng là cây khung lớn nhất bởi tổng trọng số của $T'$ không nhỏ hơn tổng trọng số của $T$.
Mệnh đề vì thế vẫn tiếp tục được thỏa bởi $M \cup \{e\}$ là tập con của tập cạnh $T'$ của một cây khung lớn nhất.

:::

#### Độ Phức Tạp

- Ý tưởng trên có thể được cài đặt với độ phức tạp thời gian $O(m \log m + n)$ bằng cách sử dụng cấu trúc dữ liệu [Disjoint Set Union](https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html) để quản lý các thành phần liên thông như trong bài toán tìm [cây khung nhỏ nhất](https://en.wikipedia.org/wiki/Minimum_spanning_tree).
:::spoiler Giải thích
- Bước khởi tạo cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) có thể có độ phức tạp $O(n)$.
- Bước sắp xếp cạnh có độ phức tạp $O(m \log m)$.
- Với mỗi lần xem xét một cạnh $e = (u, v)$, ta cần kiểm tra hai đỉnh của cạnh $e$ có cùng thuộc một thành phần liên thông không và nếu không thuộc thì ta có gộp hai thành phần liên thông chứa $u$ và $v$ lại. Nếu ta cài đặt cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) với cả hai phương pháp gộp theo kính cỡ và nén đường đi, một lần xem xét thêm cạnh như trên có độ phức tạp $O(\alpha(n))$ với $\alpha$ là hàm [Ackermann](https://en.wikipedia.org/wiki/Ackermann_function) nghịch đảo.
Vì ta duyệt $m$ cạnh, bước xém xét hết tất cả các cạnh sẽ có độ phức tạp $O(m \cdot \alpha(n))$.
Độ phức tạp tổng lúc này sẽ là $O(m \log m) + O(m \cdot \alpha(n)) + O(n) = O(m \log m + n)$.
>[!Warning] Lưu ý:
>Nếu ta chỉ dùng một trong phương pháp nêu trên khi cài đặt cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union), một lần xem xét thêm cạnh như trên có độ phức tạp $O(\log(n))$. Khi này, độ phức tạp tổng sẽ là $O(m \cdot (\log(m) + \log(n)) + n)$.
:::
- Với cách cài đặt này, độ phức tạp bộ nhớ là $O(n + m)$.
:::spoiler Giải thích
- Lưu danh sách cạnh chiếm cần $O(m)$ bộ nhớ.
- Cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) cần $O(n)$ bộ nhớ.
:::

#### Code Minh Họa

:::spoiler Code C++ minh họa

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    DisjointSetUnion(const int n): roots(n, -1) {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    DisjointSetUnion dsu(n + 1);
    long long result = 0;

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges)
        if (dsu.unite(u, v))
            result += w;

    cout << result << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

:::

### [Subtask 2](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-2)

**Giới hạn:** $n \le 10^3, m \le 10^4; k \le 1000$

#### Ý Tưởng

- Giới hạn của [Subtask 2](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-2) cho phép chúng ta thực hiện ý tưởng đề cập trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1) $k$ lần mà vẫn đảm bảo được độ phức tạp thời gian cho phép.
Cụ thể hơn, với mỗi thao tác, ta có thể thực hiện lại ý tưởng trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1) rồi xóa tập cạnh được chọn bởi thao tác khỏi đồ thị để ta có thể xử lý các thao tác sau.
>[!Note] Lưu ý:
>Vì sau khi xóa cạnh khỏi đồ thị, đồ thị có thể không liên thông nữa, tập cạnh mà chúng ta cần tìm lúc này có thể là một [rừng](https://en.wikipedia.org/wiki/Tree_(graph_theory)) thay vì chỉ một cây khung: với mỗi thành phần liên thông trong đồ thị hiện tại, ta cần tìm cây khung lớn nhất trong thành phần liên thông đó; tập cạnh chúng ta cần tìm sẽ là tập cạnh được tạo bởi các cạnh của các khung đó.

#### Độ Phức Tạp

- Ý tưởng trên có thể được cài đặt với độ phức tạp $O(m \log m + k \cdot (n + m \cdot \alpha(n)))$.
- Độ phức tạp bộ nhớ sẽ tương tự như trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1), tức $O(n + m)$.

#### Code Minh Họa

:::spoiler Code C++ minh họa

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion(const int n): roots(n, -1) {};

    void reload() {
        fill(roots.begin(), roots.end(), -1);
    }

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    DisjointSetUnion dsu(n + 1);
    vector<bool> removed(m);
    long long result = 0;

    sort(edges.rbegin(), edges.rend());

    for (int t = 0; t < k; ++t) {
        result = 0;
        dsu.reload();

        for (int i = 0; i < m; ++i) {
            if (removed[i])
                continue;
            const auto &[w, u, v] = edges[i];
            if (dsu.unite(u, v)) {
                removed[i] = true;
                result += w;
            }
        }

        cout << result << '\n';
    }
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

:::

### [Subtask 3](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-3)

**Giới hạn:** $n \le 10^3, m \le 5 \times 10^5; k \le 10^4$

#### Ý Tưởng

- Đặt $S_{i, j}$ (với $1 \leq i \leq k$ và $0 \leq j \leq m$) là tập cạnh được chọn trong thao tác thứ $i$ sau khi đã xét $j$ cạnh trong danh sách các cạnh được sắp xếp theo trọng số giảm dần.
:::spoiler Chi tiết và ví dụ
>[!Warning] Lưu ý:
>Phần này trình bày chi tiết cách xác định tập cạnh $S_{i, j}$ theo định nghĩa trên. Nội dung này có thể không bắt buộc phải đọc để hiểu ý tưởng chính, mà chỉ nhằm làm rõ hơn định nghĩa $S_{i, j}$.

**Chi Tiết**
- Với $j = 0$, ta có $S_{i,j} = \emptyset$ vì chưa có cạnh nào được xét ở thời điểm bắt đầu thao tác thứ $i$.
- Với $1 \leq j \leq m$, đặt $e$ là cạnh thứ $j$. Khi đó, ta có thể xác định $S_{i, j}$ như sau:
- $S_{i, j} = S_{i, j - 1}$ nếu một trong hai điều kiện sau thỏa:
- Cạnh $e$ đã được chọn trước đó: $\exists z ((1 \leq z < i) \land (e \in S_{z,j}))$
- Việc thêm cạnh $e$ sẽ tạo thành một chu trình trong tập hiện tại: $S_{i, j - 1} \cup \{e\}$ chứa ít nhất một chu trình.
- $S_{i, j} = S_{i, j - 1} \cup \{e\}$ trong trường hợp còn lại.

**Ví dụ**

- Với [test ví dụ thứ hai](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Sample-2), các cạnh sau khi được sắp xếp giảm dần theo trọng số có thứ tự như sau:

$$
\begin{array}{|c|*{8}{c|}}
\hline
\textbf{i} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline
e_i & (1,2) & (2,3) & (3,4) & (4,5) & (1,5) & (2,5) & (1,3) & (2,4) \\ \hline
w_i & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 \\ \hline
\end{array}
$$

- Giá trị $S_{i, j}$ được tính như bảng sau:

$$
\begin{array}{|c|*{3}{l|}}
\hline
\textbf{$j \backslash i$} & \textbf{1} & \textbf{2} & \textbf{3} \\ \hline
0 & \emptyset & \emptyset & \emptyset \\ \hline
1 & \{(1,2)\} & \emptyset & \emptyset \\ \hline
2 & \{(1,2), (2,3)\} & \emptyset & \emptyset \\ \hline
3 & \{(1,2), (2,3), (3,4)\} & \emptyset & \emptyset \\ \hline
4 & \{(1,2), (2,3), (3,4), (4,5)\} & \emptyset & \emptyset \\ \hline
5 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5)\} & \emptyset \\ \hline
6 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5)\} & \emptyset \\ \hline
7 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5), (1, 3)\} & \emptyset \\ \hline
8 & \{(1,2), (2,3), (3,4), (4,5)\} & \{(1, 5), (2, 5), (1, 3), (2, 4)\} & \emptyset \\ \hline
\end{array}
$$

:::
- Ta nhận thấy rằng nếu cạnh thứ $j$, gọi là $e_j$, được chọn trong bất kì một thao tác $i$ nào thì $i$ chính là giá trị nhỏ nhất sao cho với mọi thao tác $z$ trước $i$ ($1 \leq z < i$), việc thêm $e_j$ vào $S_{z, j - 1}$ sẽ tạo thành chu trình. Nếu không, cạnh $e_j$ đã nên được chọn trước thao tác $i$. Ta có:
$$i = \min\{x \mid \forall z ((1 \leq z < x) \rightarrow C(S_{z, j - 1} \cup \{e_j\})) \}$$ với $C$ là mệnh đề *"đồ thị con tạo bởi tập cạnh $A$ chứa ít nhất một chu trình"*.

- Dựa vào nhận xét trên, ta có thể duyệt qua từng cạnh và dùng [kỹ thuật chặt nhị phân](https://wiki.vnoi.info/algo/basic/Binary-Search) để xác định thao tác sớm nhất có thể chứa cạnh đó mà không tạo chu trình.
Để kiểm tra việc một chu trình có thể xuất hiện hay không khi thêm một cạnh nào đó, với mỗi thao tác, ta sử dụng một cấu trúc dữ liệu để quản lý thành phần liên thông trong suốt quá trình duyệt qua các cạnh.
**Ý tưởng cài đặt**: Ta có thể sử dụng $k$ cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) để quản lý thành phần liên thông giữa $n$ đỉnh cho $k$ thao tác.

#### Độ Phức Tạp

- Ý tưởng trên có thể được cài đặt với độ phức tạp $O(m \log m + k \cdot n + m \log k \cdot \alpha(n))$.
:::spoiler Giải thích
- Bước sắp xếp cạnh có độ phức tạp $O(m \log m)$ (tương tự như trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1)).
- Việc khởi tạo $k$ cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) để quản lý thành phần liên thông trên $n$ đỉnh có độ phức tạp $O(k \cdot n)$.
- Bước xử lý các cạnh có độ phức tạp $O(m \log k \cdot \alpha(n))$.
- Với mỗi lần xét cạnh, chúng ta tìm được thao tác (nếu tồn tại) mà chứa được cạnh đang xét sau tối đa $O(\log k)$ bước chặt nhị phân.
- Với mỗi lần chặt nhị phân, việc kiểm tra việc hai đỉnh của cạnh đang xét có đang thuộc cùng một thành phần liên thông có độ phức tạp $O(\alpha(n))$ (tương tự như trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1)).
- Chúng ta phải xét qua $O(m)$ cạnh.
- Ngoài ra, chúng ta có thể phải cập nhật thành phần liên thông cuối mỗi lần xét cạnh với độ phức tạp $O(\alpha(n))$.
Độ phức tạp tổng vì thế là $O(m \cdot (\log k \cdot \alpha(n) + \alpha(n))) = O(m \log k \cdot \alpha(n))$
:::
- Với cách cài đặt này, độ phức tạp bộ nhớ là $O(m + k \cdot n)$.
:::spoiler Giải thích
- Lưu danh sách cạnh chiếm cần $O(m)$ bộ nhớ (tương tự như trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1)).
- Lưu $k$ cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) cần $O(k \cdot n)$ bộ nhớ.
:::

#### Code Minh Họa

:::spoiler Code C++ minh họa

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    DisjointSetUnion(const int n): roots(n, -1) {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
long long result[MAX_K];
vector<DisjointSetUnion> graphs;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    int low = 0, middle = 0, high = 0;

    graphs.resize(k + 1, DisjointSetUnion(n + 1));

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges) {
        low = 0;
        high = k + 1;
        while (low + 1 < high) {
            middle = low + high >> 1;
            if (graphs[middle].checkConnected(u, v))
                low = middle;
            else
                high = middle;
        }
        if (high <= k) {
            graphs[high].unite(u, v);
            result[high] += w;
        }
    }

    for (int i = 1; i <= k; ++i)
        cout << result[i] << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

:::

### [Subtask 4](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-4)

**Giới hạn:** $n \le 10^5, m \le 5 \times 10^5; k \le 10^4$

#### Ý Tưởng

>[!Note] Lưu ý:
>Ý tưởng chính sử dụng trong [Subtask](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-4) này cũng giống như trong [Subtask 3](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-3). Điểm khác biệt chính nằm ở hướng cài đặt ý tưởng.
- :::spoiler Nhận xét về độ phức tạp của cách cài đặt cho Subtask 3
Với [độ phức tạp](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#%C4%90%E1%BB%99-Ph%E1%BB%A9c-T%E1%BA%A1p26) của [cách cài đặt](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#%C3%9D-T%C6%B0%E1%BB%9Fng25) cho [Subtask 3](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-3), ta nhận thấy rằng việc quản lý các thành phần liên thông cho từng thao tác, là phần có chi phí tính toán nặng trong trường hợp tệ nhất (với độ phức tạp $O(k \cdot n)$).
Mặt khác, các bước xử lý còn lại có chi phí tính toán chấp nhận được.
Vì vậy, nếu ta muốn cải thiện ý tưởng đó, ta cần phải tối ưu những bước xử lý liên quan tới quản lý thành phần liên thông.
:::
- Ta có một số nhận xét như sau:
- Với cách cài đặt đề cập trong [Subtask 3](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-3), ta cần phải quan lý tổng cộng $k \cdot n$ đỉnh (mỗi cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) quản lý $n$ đỉnh).
Tuy nhiên, trong suốt quá trình xử lý $m$ cạnh, chỉ có tối đa $2 \cdot m$ đỉnh thuộc các thành phần liên thông có kích thước lớn hơn $1$.
:::spoiler Giải thích
Mỗi cạnh được xét nếu được thêm vào chỉ có thể làm tăng số lượng đỉnh nằm trong một thành phần liên thông không đơn lẻ thêm tối đa $2$ đỉnh
:::
- Khi kiểm tra hai đỉnh $u$ và $v$ khác nhau có thuộc cùng một thành phần liên thông hay không, ta nhận thấy rằng: *nếu một trong hai đỉnh thuộc một thành phần có kích thước bằng $1$ thì $u$ và $v$ chắc chắn không cùng thành phần liên thông*.
$\Rightarrow$ Dựa trên những nhận xét trên, ta chỉ cần quản lý các thành phần liên thông có kích thước ít nhất là $2$ đỉnh, và xử lý riêng các trường hợp thành phần liên thông chỉ có một đỉnh.
Về **mặt cài đặt**, ta chỉ cần thêm đỉnh vào cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) khi ta cần gộp thành phần liên thông của đỉnh đó với đỉnh khác.

#### Độ Phức Tạp

- Ý tưởng trên có thể được cài đặt với độ phức tạp $O(m \log m + k + m \log k \cdot \alpha(n))$.
:::spoiler Giải thích
- Việc quản lý các thành phần liên thông giờ đây chỉ có độ phức tạp $O(k)$ để khởi tạo và $O(m)$ để thêm đỉnh khi xử lý tất cả $m$ cạnh.
Vì thế độ phức tạp tổng của cách cài đặt là $O(m \log m) + O(k) + O(m) + O(m \log k \cdot \alpha(n)) = O(m \log m + k + m \log k \cdot \alpha(n))$
:::

- Với cách cài đặt này, độ phức tạp bộ nhớ là $O(m + k)$.
:::spoiler Giải thích
- Lưu danh sách cạnh chiếm cần $O(m)$ bộ nhớ như trong [Subtask 1](https://hackmd.io/gh_66Q-xSKqyFfNKiMSmPQ#Subtask-1).
- Lưu $k$ cấu trúc dữ liệu [Disjoint Set Union](https://wiki.vnoi.info/algo/data-structures/disjoint-set-union) cần $O(k)$ bộ nhớ và cần thêm $O(m)$ bộ nhớ do chúng ta có thể thêm tối đa $2 \cdot m$ đỉnh.
$\Rightarrow$ Độ phức tạp tổng của cách cài đặt là $O(m) + O(m) + O(k) = O(m + k)$.
:::

#### Code Minh Họa

:::spoiler Code C++ minh họa

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

class DisjointSetUnion {
private:

    mutable vector<int> roots;

public:

    DisjointSetUnion() {};

    int getRoot(const int x) const {
        return (roots[x] < 0) ? x : (roots[x] = getRoot(roots[x]));
    }

    bool checkConnected(const int x, const int y) const {
        return getRoot(x) == getRoot(y);
    }

    int addVertex() {
        const int result = roots.size();
        roots.push_back(-1);
        return result;
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y)
            return false;
        if (roots[x] > roots[y])
            swap(x, y);
        roots[x] += roots[y];
        roots[y] = x;
        return true;
    }

};

class UndirectedGraph {
private:

    unordered_map<int, int> ids;
    DisjointSetUnion dsu;

public:

    bool checkConnected(const int x, const int y) const {
        const auto a = ids.find(x);
        if (a == ids.end())
            return false;
        const auto b = ids.find(y);
        if (b == ids.end())
            return false;
        return dsu.checkConnected(a -> second, b -> second);
    }

    int getID(const int x) {
        const auto a = ids.find(x);
        if (a == ids.end())
            return ids[x] = dsu.addVertex();
        return a -> second;
    }

    bool unite(const int x, const int y) {
        return dsu.unite(getID(x), getID(y));
    }

};

constexpr int MAX_N = 1E5 + 5, MAX_M = 1E5 + 5, MAX_K = 1E4 + 4;

int n, m, k;
long long result[MAX_K];
vector<UndirectedGraph> graphs;
vector<tuple<int, int, int> > edges;

void input() {
    cin >> n >> m >> k;

    edges.resize(m);

    for (auto &[w, u, v] : edges)
        cin >> u >> v >> w;
}

void solve() {
    int low = 0, middle = 0, high = 0;

    graphs.resize(k + 1);

    sort(edges.rbegin(), edges.rend());

    for (const auto &[w, u, v] : edges) {
        low = 0;
        high = k + 1;
        while (low + 1 < high) {
            middle = low + high >> 1;
            if (graphs[middle].checkConnected(u, v))
                low = middle;
            else
                high = middle;
        }
        if (high <= k) {
            graphs[high].unite(u, v);
            result[high] += w;
        }
    }

    for (int i = 1; i <= k; ++i)
        cout << result[i] << '\n';
}

signed main() {
    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL

    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    input();
    solve();

    return 0;
}

:::