Tổng quan bài toán

Bài toán yêu cầu quản lý một cấu trúc cây, trong đó các đỉnh có thể được kích hoạt hoặc vô hiệu hóa theo thời gian thực. Với mỗi trạng thái, cần tính toán tổng trọng số cạnh nhỏ nhất để nối tất cả các đỉnh đang được kích hoạt lại với nhau thành một thành phần liên thông.

Phân tích thuật toán

Giả sử các đỉnh đang hoạt động được sắp xếp theo thứ tự thời gian vào (DFS order) là $v_1, v_2, ..., v_k$. Tổng độ dài cạnh cần thiết để nối chúng thành một chu trình ảo (sau đó chia đôi để lấy cây khung nhỏ nhất) được tính bằng công thức:

$$ \text{Cost} = \frac{1}{2} \left( \sum_{i=1}^{k-1} \text{dist}(v_i, v_{i+1}) + \text{dist}(v_k, v_1) \right) $$

Trong đó $\text{dist}(u, v)$ là khoảng cách giữa hai đỉnh $u$ và $v$ trên cây. Để duy trì giá trị này động, ta cần một cấu trúc dữ liệu hỗ trợ chèn, xóa và tìm kiếm phần tử lân cận nhanh chóng. std::set trong C++ là một lựa chọn phù hợp nếu được tùy chỉnh bộ so sánh.

Triển khai std::set với bộ so sánh tùy chỉnh

Thông thường, std::set sắp xếp theo giá trị phần tử. Tuy nhiên, trong bài toán cây, ta cần sắp xếp các đỉnh theo thứ tự DFS. Điều này đòi hỏi việc overload toán tử so sánh.

Định nghĩa cấu trúc so sánh

Thay vì sử dụng toán tử < mặc định, ta định nghĩa một struct riêng biệt để so sánh dựa trên mảng thời gian DFS:

struct DfsComparator {
    bool operator()(int u, int v) const {
        return discovery_time[u] < discovery_time[v];
    }
};

Khi khai báo set, ta truyền struct này vào template:

std::set<int, DfsComparator> active_nodes;

Xử lý vòng quanh với Iterator

Do công thức tính cost yêu cầu nối đỉnh cuối cùng với đỉnh đầu tiên (tính chất vòng tròn), việc tìm phần tử liền trước và liền sau cần xử trường hợp biên. Nếu phần tử đang xét là đầu tiên, phần tử trước đó sẽ là phần tử cuối cùng của set và ngược lại.

Việc sử dụng auto giúp code ngắn gọn hơn khi làm việc với iterator phức tạp của set.

Mã nguồn tham khảo

Dưới đây là phiên bản code đã được tối ưu và đặt tên biến rõ ràng hơn, sử dụng kỹ thuật Binary Lifting để tìm LCA và khoảng cách.

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

const int MAXN = 100005;
const int LOGN = 20;

int num_nodes, num_queries;
vector<tuple<int, int>> adj[MAXN];
int up[MAXN][LOGN];
long long dist_up[MAXN][LOGN];
int depth[MAXN];
int discovery_time[MAXN];
int timer_dfs;

void dfs(int u, int p, int d, long long current_dist) {
    discovery_time[u] = ++timer_dfs;
    depth[u] = d;
    dist_up[u][0] = current_dist;
    up[u][0] = p;

    for (int i = 1; i < LOGN; ++i) {
        int ancestor = up[u][i - 1];
        if (ancestor == 0) break;
        up[u][i] = up[ancestor][i - 1];
        dist_up[u][i] = dist_up[u][i - 1] + dist_up[ancestor][i - 1];
    }

    for (auto& edge : adj[u]) {
        int v = get<0>(edge);
        int w = get<1>(edge);
        if (v != p) {
            dfs(v, u, d + 1, w);
        }
    }
}

long long get_path_distance(int u, int v) {
    long long total_dist = 0;
    if (depth[u] < depth[v]) swap(u, v);

    for (int i = LOGN - 1; i >= 0; --i) {
        if (up[u][i] && depth[up[u][i]] >= depth[v]) {
            total_dist += dist_up[u][i];
            u = up[u][i];
        }
    }

    if (u == v) return total_dist;

    for (int i = LOGN - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            total_dist += dist_up[u][i] + dist_up[v][i];
            u = up[u][i];
            v = up[v][i];
        }
    }

    total_dist += dist_up[u][0] + dist_up[v][0];
    return total_dist;
}

struct DfsComparator {
    bool operator()(int u, int v) const {
        return discovery_time[u] < discovery_time[v];
    }
};

set<int, DfsComparator> active_nodes;
long long current_total_cost = 0;

void activate_node(int u) {
    active_nodes.insert(u);
    auto it = active_nodes.find(u);
    
    auto prev_it = (it == active_nodes.begin()) ? prev(active_nodes.end()) : prev(it);
    auto next_it = next(it);
    if (next_it == active_nodes.end()) next_it = active_nodes.begin();

    int l = *prev_it;
    int r = *next_it;

    current_total_cost -= get_path_distance(l, r);
    current_total_cost += get_path_distance(l, u);
    current_total_cost += get_path_distance(u, r);
}

void deactivate_node(int u) {
    auto it = active_nodes.find(u);
    
    auto prev_it = (it == active_nodes.begin()) ? prev(active_nodes.end()) : prev(it);
    auto next_it = next(it);
    if (next_it == active_nodes.end()) next_it = active_nodes.begin();

    int l = *prev_it;
    int r = *next_it;

    current_total_cost += get_path_distance(l, r);
    current_total_cost -= get_path_distance(l, u);
    current_total_cost -= get_path_distance(u, r);

    active_nodes.erase(it);
}

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

    if (!(cin >> num_nodes)) return 0;

    for (int i = 0; i < num_nodes - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(1, 0, 0, 0);

    cin >> num_queries;
    while (num_queries--) {
        char type;
        cin >> type;
        if (type == '?') {
            cout << current_total_cost / 2 << "\n";
        } else {
            int x;
            cin >> x;
            if (type == '+') activate_node(x);
            else deactivate_node(x);
        }
    }

    return 0;
}

Lưu ý rằng việc sử dụng std::set với comparator dựa trên biến toàn cục yêu cầu biến đó không thay đổi ý nghĩa trong suốt vòng đời của set. Trong bài toán này, thứ tự DFS là cố định nên hoàn toàn an toàn. Khi làm việc với các comparator phức tạp hơn (ví dụ liên quan đến số thực), cần đảm bảo tính bắc cầu để tránh lỗi logic khi tìm kiếm phần tử.