Hướng giải của XOR đường đi

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

Sử dụng thuật toán phù hợp để giải quyết bài toán.

Lời giải

Dùng kỹ thuật RMQ (Range Minimum Query) với Sparse Table hoặc Segment Tree.

XOR có tính chất đặc biệt: \(a \oplus a = 0\) (tự triệt tiêu). Nhờ đó, ta có thể tính XOR trên đường đi chỉ với Euler Tour + prefix XOR.

Tư tưởng:

  • Gán mỗi cạnh cho đỉnh con. Tính \(xorFromRoot[v]\) = XOR các cạnh từ gốc \(1\) đến \(v\).
  • Khi đó: \(pathXOR(u, v) = xorFromRoot[u] \oplus xorFromRoot[v]\) (vì đoạn từ gốc đến LCA xuất hiện hai lần và tự triệt tiêu).
  • Cần tìm LCA để đảm bảo công thức trên đúng cho mọi trường hợp — tuy nhiên trên thực tế với edge weights, công thức trên đã đủ.
// Giải thuật rmqt cho bài toán rmqt-xor-path\n#include <bits/stdc++.h>
using namespace std;

int main() {
    // Doc du lieu dau vao
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n; cin >> n;
    vector<vector<pair<int,int>>> adj(n+1);
    for (int i=0; i<n-1; i++) {
        int u,v,w; cin>>u>>v>>w;
        adj[u].push_back({v,w}); adj[v].push_back({u,w});
    }

    vector<long long> xr(n+1, 0);
    vector<int> depth(n+1, 0);

    function<void(int,int)> dfs = [&](int u, int p) {
        for (auto [v,w] : adj[u]) if (v != p) {
            depth[v] = depth[u] + 1;
            xr[v] = xr[u] ^ w;
            dfs(v, u);
        }
    };
    dfs(1, 0);

    int LOG = __lg(n) + 1;
    vector<vector<int>> up(n+1, vector<int>(LOG, 0));
    for (int i=2; i<=n; i++)
        for (auto [v,w] : adj[i])
            if (depth[v] < depth[i]) { up[i][0]=v; break; }
    for (int j=1; j<LOG; j++)
        for (int i=1; i<=n; i++) up[i][j] = up[up[i][j-1]][j-1];

    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u,v);
        int d = depth[u] - depth[v];
        for (int j=0; j<LOG; j++) if (d & (1<<j)) u = up[u][j];
        if (u == v) return u;
        for (int j=LOG-1; j>=0; j--)
            if (up[u][j] != up[v][j]) { u=up[u][j]; v=up[v][j]; }
        return up[u][0];
    };

    int q; cin >> q;
    while (q--) {
        int u,v; cin >> u >> v;
        cout << (xr[u] ^ xr[v]) << "\n";
    }
    return 0;
}

Độ phức tạp: \(O(N)\).

Nhận xét

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