Hướng giải của Tìm đỉnh gần nhất

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

Lời giải

Ý tưởng

Bài toán QTREE5 kinh điển. Sử dụng Centroid Decomposition:

Với mỗi centroid, lưu một multiset chứa khoảng cách từ nó đến tất cả các đỉnh được đánh dấu trong subtree của nó.
Khi bật/tắt một đỉnh \(u\), duyệt từ \(u\) lên centroid tree, tại mỗi ancestor \(c\), cập nhật multiset[c] với \(dist(u,c)\).
Khi truy vấn \(u\), duyệt từ \(u\) lên centroid tree, lấy \(dist(u,c) + min(multiset[c])\).
Cần LCA để tính khoảng cách \(O(\log N)\).

Độ phức tạp

Khởi tạo: \(O(N \log N)\).
Mỗi truy vấn: \(O(\log^2 N)\).

Code mẫu

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

const int MAXN = 100005, LOG = 17;
vector<int> adj[MAXN];
int subsize[MAXN], depth[MAXN], up[MAXN][LOG];
int centroid_parent[MAXN];
bool removed[MAXN], colored[MAXN];
multiset<int> color_dist[MAXN];
int n;

void dfs_lca(int u, int p) {
    // Chuẩn bị LCA
    up[u][0] = p;
    for (int i = 1; i < LOG; i++) {
        if (up[u][i-1] != -1)
            up[u][i] = up[up[u][i-1]][i-1];
        else
            up[u][i] = -1;
    }
    for (int v : adj[u]) {
        if (v != p) {
            depth[v] = depth[u] + 1;
            dfs_lca(v, u);
        }
    }
}

int lca(int u, int v) {
    // Tìm LCA
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG-1; i >= 0; i--)
        if (up[u][i] != -1 && depth[up[u][i]] >= depth[v])
            u = up[u][i];
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; i--)
        if (up[u][i] != up[v][i])
            u = up[u][i], v = up[v][i];
    return up[u][0];
}

int dist(int u, int v) {
    // Tính khoảng cách
    int l = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[l];
}

void dfs_size(int u, int p) {
    subsize[u] = 1;
    for (int v : adj[u])
        if (v != p && !removed[v]) {
            dfs_size(v, u);
            subsize[u] += subsize[v];
        }
}

int find_centroid(int u, int p, int tot) {
    for (int v : adj[u])
        if (v != p && !removed[v] && subsize[v] > tot / 2)
            return find_centroid(v, u, tot);
    return u;
}

void decompose(int u, int pc) {
    // Xây centroid tree
    dfs_size(u, -1);
    int c = find_centroid(u, -1, subsize[u]);
    centroid_parent[c] = pc;
    removed[c] = true;
    for (int v : adj[c])
        if (!removed[v]) decompose(v, c);
}

void toggle(int u) {
    // Bật/tắt đỉnh u, cập nhật tất cả ancestor trên centroid tree
    int cur = u;
    while (cur != -1) {
        int d = dist(u, cur);
        if (colored[u]) {
            auto it = color_dist[cur].find(d);
            if (it != color_dist[cur].end())
                color_dist[cur].erase(it);
        } else {
            color_dist[cur].insert(d);
        }
        cur = centroid_parent[cur];
    }
    colored[u] = !colored[u];
}

int query(int u) {
    // Tìm đỉnh được đánh dấu gần u nhất
    int ans = INT_MAX;
    int cur = u;
    while (cur != -1) {
        if (!color_dist[cur].empty()) {
            ans = min(ans, dist(u, cur) + *color_dist[cur].begin());
        }
        cur = centroid_parent[cur];
    }
    return ans == INT_MAX ? -1 : ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    depth[1] = 0;
    memset(up, -1, sizeof(up));
    dfs_lca(1, -1);
    decompose(1, -1);
    int q; cin >> q;
    while (q--) {
        int t, u; cin >> t >> u;
        if (t == 1) toggle(u);
        else cout << query(u) << "\n";
    }
    return 0;
}

Nhận xét

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