Hợp nhất heuristic trên cây (DSU on Tree) là một kỹ thuật hiệu quả để giải quyết các bài toán thống kê trên cây tĩnh với độ phức tạp thời gian O(n log n). Phương pháp này tập trung vào việc tối ưu hóa quá trình hợp nhất các thông tin từ các cây con, giảm thiểu tính toán trùng lặp, đặc biệt phù hợp với các truy vấn trên cây không có yêu cầu sửa đổi.

Nguyên lý cốt lõi

Ý tưởng chính của Hợp nhất heuristic trên cây dựa trên đặc điểm của phân tách nhánh nặng-nhẹ. Thuật toán ưu tiên xử lý các cây con nhẹ trước, đồng thời giữ lại thông tin của cây con nặng. Bằng cách này, việc tính toán lại các giá trị đã có được loại bỏ, giúp giảm độ phức tạp từ O(n^2) xuống còn O(n log n). Các bước thực hiện bao gồm:

1. Xác định nhánh nặng: Sử dụng một lượt duyệt DFS để đánh dấu con nặng của mỗi nút.
2. Duyệt đệ quy cây con nhẹ: Xử lý đệ quy các cây con nhẹ và xóa bỏ các thông tin thống kê đã thu thập.
3. Xử lý cây con nặng: Giữ lại thông tin của cây con nặng để tránh tính toán lại.
4. Hợp nhất thông tin nút hiện tại: Kết hợp thông tin của nút hiện tại với thông tin từ cây con nặng.

Chi tiết triển khai

Bước 1: Tiền xử lý nhánh nặng

Tính toán kích thước cây con và đánh dấu nhánh nặng bằng DFS:

void dfs_find_heavy_child(int currentNode, int parentNode) {
    subtree_size[currentNode] = 1;
    int largest_child_size = 0;
    heavy_child[currentNode] = -1; // Khởi tạo con nặng là -1

    for (int neighbor : adjacencyList[currentNode]) {
        if (neighbor != parentNode) {
            dfs_find_heavy_child(neighbor, currentNode);
            subtree_size[currentNode] += subtree_size[neighbor];
            if (subtree_size[neighbor] > largest_child_size) {
                largest_child_size = subtree_size[neighbor];
                heavy_child[currentNode] = neighbor;
            }
        }
    }
}
    

Bước 2: Duyệt đệ quy các cây con

Quyết định có giữ lại thông tin thống kê hay không dựa trên việc nút đó có phải là con nặng hay không:

void process_tree(int currentNode, int parentNode, bool keep_info) {
    // Duyệt qua các cây con nhẹ trước
    for (int neighbor : adjacencyList[currentNode]) {
        if (neighbor != parentNode && neighbor != heavy_child[currentNode]) {
            process_tree(neighbor, currentNode, false); // Không giữ thông tin cho cây con nhẹ
        }
    }

    // Nếu có con nặng, duyệt đệ quy cây con nặng và giữ lại thông tin
    if (heavy_child[currentNode] != -1) {
        process_tree(heavy_child[currentNode], currentNode, true);
    }

    // Xử lý thông tin cho nút hiện tại và các cây con nhẹ đã duyệt qua
    // (Phần này phụ thuộc vào bài toán cụ thể, ví dụ: cập nhật các bộ đếm,
    // thêm các phần tử vào cấu trúc dữ liệu, tính toán kết quả...)
    // Ví dụ: merge_node_data(currentNode, parentNode);
}