Hướng giải của Tần Suất Màu Sắc Cây Con

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu thống kê màu sắc xuất hiện đúng \(K\) lần trong gia phả cây con của mỗi đỉnh. Chúng ta áp dụng kỹ thuật Gộp cây phân đoạn (Segment Tree Merging) kết hợp duy trì giá trị trực tiếp tại mỗi nút:

  1. Tại mỗi nút của cây dòng họ, ta khởi tạo một Segment Tree động quản lý tần suất của các màu sắc.
  2. Để kiểm soát chính xác số màu xuất hiện đúng \(K\) lần trong \(O(1)\), tại mỗi node của Segment Tree ta lưu thêm trường exact_k: số lượng màu sắc đạt tần suất đúng bằng \(K\).
  3. Khi duyệt DFS và gộp cây phân đoạn con lên cha (destructive merge):
    • Ta gộp trực tiếp để tiết kiệm bộ nhớ: roots[u] = merge_segtree(roots[u], roots[child]).
    • Tại nút lá quản lý tần suất màu, nếu count sau khi cộng dồn bằng \(K\), ta gán exact_k = 1, ngược lại bằng \(0\).
    • Các nút trong cập nhật exact_k = exact_k[left] + exact_k[right].
    • Đáp án cho nút \(U\) chính là tree[roots[U]].exact_k lấy ra trong \(O(1)\).

Độ phức tạp thời gian tổng cộng: \(O(N \log N)\), bộ nhớ cực kỳ an toàn.

Mã nguồn C++ mẫu

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

struct Node {
    int count;
    int exact_k;
    int left, right;
};

vector<Node> tree;
int k_target;
vector<int> colors, roots, ans;
vector<vector<int>> adj;

int create_node() {
    tree.push_back({0, 0, -1, -1});
    return tree.size() - 1;
}

int update(int prev_id, int start, int end, int pos, int val) {
    int id = create_node();
    if (prev_id != -1) tree[id] = tree[prev_id];
    tree[id].count += val;
    if (start == end) {
        tree[id].exact_k = (tree[id].count == k_target);
        return id;
    }
    int mid = (start + end)/2;
    if (pos <= mid) {
        int new_left = update(tree[id].left, start, mid, pos, val);
        tree[id].left = new_left;
    } else {
        int new_right = update(tree[id].right, mid+1, end, pos, val);
        tree[id].right = new_right;
    }

    int l_exact = (tree[id].left != -1) ? tree[tree[id].left].exact_k : 0;
    int r_exact = (tree[id].right != -1) ? tree[tree[id].right].exact_k : 0;
    tree[id].exact_k = l_exact + r_exact;
    return id;
}

int merge_segtree(int node1, int node2, int start, int end) {
    if (node1 == -1) return node2;
    if (node2 == -1) return node1;
    if (start == end) {
        tree[node1].count += tree[node2].count;
        tree[node1].exact_k = (tree[node1].count == k_target);
        return node1;
    }
    int mid = (start + end)/2;
    int new_left = merge_segtree(tree[node1].left, tree[node2].left, start, mid);
    tree[node1].left = new_left;
    int new_right = merge_segtree(tree[node1].right, tree[node2].right, mid+1, end);
    tree[node1].right = new_right;

    int l_exact = (tree[node1].left != -1) ? tree[tree[node1].left].exact_k : 0;
    int r_exact = (tree[node1].right != -1) ? tree[tree[node1].right].exact_k : 0;
    tree[node1].exact_k = l_exact + r_exact;
    tree[node1].count = (tree[node1].left != -1 ? tree[tree[node1].left].count : 0) + 
                        (tree[node1].right != -1 ? tree[tree[node1].right].count : 0);
    return node1;
}

int max_color_val = 1;

void dfs(int v, int p) {
    roots[v] = update(-1, 1, max_color_val, colors[v], 1);
    for (int c : adj[v]) {
        if (c != p) {
            dfs(c, v);
            roots[v] = merge_segtree(roots[v], roots[c], 1, max_color_val);
        }
    }
    ans[v] = (roots[v] != -1) ? tree[roots[v]].exact_k : 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; if (!(cin >> n >> k_target)) return 0;
    colors.resize(n+1); roots.assign(n+1, -1); ans.assign(n+1, 0);
    vector<int> temp;
    for (int i=1; i<=n; i++) {
        cin >> colors[i];
        temp.push_back(colors[i]);
    }
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    auto get_compressed = [&](int v) {
        return lower_bound(temp.begin(), temp.end(), v) - temp.begin() + 1;
    };
    for (int i=1; i<=n; i++) {
        colors[i] = get_compressed(colors[i]);
    }
    max_color_val = temp.size();

    adj.resize(n+1);
    for (int i=0; i<n-1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    tree.push_back({0, 0, -1, -1}); // dummy root
    dfs(1, 0);
    for (int i=1; i<=n; i++) cout << ans[i] << " ";
    cout << "\n";
}

Nhận xét

Không có ý kiến tại thời điểm này.