Hướng giải của [Mo's] Trên Cây

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 truy vấn trên đường đi của cây. Sử dụng Mo's Algorithm trên cây (Mo's on Trees).

Ý tưởng:

  • Dùng Euler Tour để chuyển cây thành mảng \(2N\) phần tử (mỗi đỉnh xuất hiện hai lần: lúc vào và lúc ra).
  • Mỗi truy vấn \((U, V)\) (giả sử \(in[U] \le in[V]\)):
    • Nếu \(U\) là tổ tiên của \(V\): đoạn \([in[U], in[V]]\).
    • Ngược lại: đoạn \([out[U], in[V]]\) cộng thêm \(LCA(U,V)\).
  • Dùng mảng visited[] (XOR trick): khi một đỉnh xuất hiện lần thứ hai trong đoạn, nó bị loại khỏi kết quả (vì không nằm trên đường đi).
  • Hàm toggle(v): nếu visited[v] là true, xóa khỏi kết quả; ngược lại, thêm vào.

Độ phức tạp: \(O((N+Q)\sqrt{N})\).

Mã nguồn C++

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

const int LOG = 17;

vector<vector<int>> adj;
vector<int> val, euler, in, out, depth, par[LOG];
int timer, blockSize;

struct Query {
    int l, r, lca, idx;
    bool operator<(const Query& o) const {
        int bl = l / blockSize, br = o.l / blockSize;
        if (bl != br) return bl < br;
        return (bl & 1) ? (r > o.r) : (r < o.r);
    }
};

void dfs(int u, int p) {
    in[u] = timer;
    euler[timer++] = u;
    par[0][u] = p;
    depth[u] = (p == -1) ? 0 : depth[p] + 1;
    for (int i = 1; i < LOG; i++)
        par[i][u] = (par[i-1][u] == -1) ? -1 : par[i-1][par[i-1][u]];
    for (int v : adj[u])
        if (v != p) dfs(v, u);
    out[u] = timer;
    euler[timer++] = u;
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = LOG - 1; i >= 0; i--)
        if (par[i][u] != -1 && depth[par[i][u]] >= depth[v])
            u = par[i][u];
    if (u == v) return u;
    for (int i = LOG - 1; i >= 0; i--)
        if (par[i][u] != par[i][v])
            u = par[i][u], v = par[i][v];
    return par[0][u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    val.resize(n);
    for (int i = 0; i < n; i++) cin >> val[i];

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

    in.resize(n); out.resize(n);
    depth.assign(n, 0);
    euler.resize(2 * n);
    for (int i = 0; i < LOG; i++) par[i].assign(n, -1);
    timer = 0;
    dfs(0, -1);

    // Nén giá trị
    vector<int> comp = val;
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for (int i = 0; i < n; i++)
        val[i] = lower_bound(comp.begin(), comp.end(), val[i]) - comp.begin();

    blockSize = max(1, (int)sqrt(2 * n));
    vector<Query> queries(q);
    for (int i = 0; i < q; i++) {
        int u, v; cin >> u >> v; u--; v--;
        if (in[u] > in[v]) swap(u, v);
        int w = lca(u, v);
        if (w == u) {
            queries[i] = {in[u], in[v], -1, i};
        } else {
            queries[i] = {out[u], in[v], w, i};
        }
    }
    sort(queries.begin(), queries.end());

    vector<int> ans(q);
    vector<int> freq(comp.size(), 0);
    vector<bool> visited(n, false);
    int distinct = 0, curL = 0, curR = -1;

    auto toggle = [&](int node) {
        if (visited[node]) {
            freq[val[node]]--;
            if (freq[val[node]] == 0) distinct--;
        } else {
            if (freq[val[node]] == 0) distinct++;
            freq[val[node]]++;
        }
        visited[node] = !visited[node];
    };

    for (auto& qr : queries) {
        while (curL > qr.l) toggle(euler[--curL]);
        while (curR < qr.r) toggle(euler[++curR]);
        while (curL < qr.l) toggle(euler[curL++]);
        while (curR > qr.r) toggle(euler[curR--]);

        if (qr.lca != -1) toggle(qr.lca);
        ans[qr.idx] = distinct;
        if (qr.lca != -1) toggle(qr.lca);
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << "\n";

    return 0;
}

Nhận xét

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