Dạng: LCA, cấu trúc dữ liệu

Yêu cầu: Cho cây ~N~ đỉnh. Truy vấn ~u~, ~v~, tìm ~LCA(u~, ~u + 1~, ~u + 2~, ~\dots~, ~v)~

Cách làm:

~LCA(u~, ~u + 1~, ~u + 2~, ~\dots~, ~v)~ ~=~ ~LCA(LCA(u~, ~u + 1~, ~\dots~, ~k~ - ~1)~, ~LCA(k~, ~k + 1~, ~\dots~, ~v))~

Vì thế bài này có thể áp dụng cấu trúc dữ liệu như IT hoặc RMQ kết hợp LCA để giải.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 100005;
using namespace std;
VI a[N];
int par[N][20], ans[N][20], d[N];
int n, q, lg;

void dfs(int u) {
    TR(v, a[u]) if (*v != par[u][0]) {
        par[*v][0] = u;
        d[*v] = d[u] + 1;
        dfs(*v);
    }
}

int lca(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    REPD(i, lg, 0) if (d[v] - d[u] >= (1 << i)) v = par[v][i];
    if (u == v) return u;
    REPD(i, lg, 0) if (par[u][i] != par[v][i]) {
        u = par[u][i]; v = par[v][i];
    }
    return par[u][0];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    int u, v;
    FOR(i, 1, n) {
        cin >> u >> v;
        a[u].PB(v); a[v].PB(u);
    }
    dfs(1);
    lg = log2(n) + 2;
    REP(j, 1, lg) REP(i, 1, n)
        par[i][j] = par[par[i][j - 1]][j - 1];
    REP(i, 1, n) ans[i][0] = i;
    REP(j, 1, lg) for(int i = 1; i + (1 << j - 1) <= n; i++)
        ans[i][j] = lca(ans[i][j - 1], ans[i + (1 << j - 1)][j - 1]);
    int i, j;
    while (q--) {
        cin >> i >> j;
        int k = log2(j - i + 1);
        cout << lca(ans[i][k], ans[j - (1 << k) + 1][k]) << '\n';
    }
    return 0;
}

Code mẫu của RR

#include <bits/stdc++.h>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)

#define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; }
#define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; }
#define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
using namespace std;

const int MN = 70111;

int n, q, h[MN];
vector<int> ke[MN];
int father[22][MN], ln[MN], res[22][MN];

void dfs(int u, int fu) {
    REP(i,ke[u].size()) {
        int v = ke[u][i];
        if (v == fu) continue;

        h[v] = h[u] + 1;
        father[0][v] = u;
        dfs(v, u);
    }
}

void init() {
    for(int i = 1, res = 0; i < MN; i *= 2, ++res)
        ln[i] = res;
    FOR(i,2,MN-1)
        if (!ln[i]) ln[i] = ln[i-1];
//    PR(ln, 10);
    FOR(lg,1,20)
        FOR(i,1,n)
            father[lg][i] = father[lg-1][father[lg-1][i]];
}

int lca(int u, int v) {
    if (u == v) return u;
    if (h[u] > h[v]) swap(u, v);
    if (h[u] < h[v]) {
        FORD(lg,20,0) {
            int x = father[lg][v];
            if (h[x] >= h[u]) {
                v = x;
            }
        }
    }
    if (u == v) return u;

    FORD(lg,20,0)
        if (father[lg][u] != father[lg][v]) {
            u = father[lg][u];
            v = father[lg][v];
        }
    return father[0][u];
}

#define TWO(X) (1<<(X))

int main() {
    ios :: sync_with_stdio(false);
    while (cin >> n >> q) {
        FOR(i,1,n) ke[i].clear();
        FOR(i,2,n) {
            int u, v; cin >> u >> v;
            ke[u].push_back(v);
            ke[v].push_back(u);
        }

        h[1] = 1;
        dfs(1, -1);
        init();

        FOR(i,1,n) res[0][i] = i;
        FOR(lg,1,20)
            FOR(i,1,n-TWO(lg)+1)
                res[lg][i] = lca(res[lg-1][i], res[lg-1][i+TWO(lg-1)]);

        while (q--) {
            int u, v; cin >> u >> v;
            int len = v - u + 1;
            int lg = ln[len];
            cout << lca(res[lg][u], res[lg][v - TWO(lg) + 1]) << "\n";
        }
    }
}

Code mẫu của skyvn97

#include<cstdio>
#include<vector>
#define MAX   100100
#define LOG   17
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define MASK(i) (1<<(i))
using namespace std;
vector<int> g[MAX];
int minLab[MAX][LOG+1],maxLab[MAX][LOG+1],lg2[MAX];
int par[MAX][LOG+1],h[MAX],lab[MAX];
int n,q,cnt;
void loadtree(void) {
    scanf("%d%d",&n,&q);
    REP(zz,n-1) {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    h[0]=-1;
}
void dfs(int u) {
    lab[u]=++cnt;
    REP(i,g[u].size()) if (g[u][i]!=par[u][0]) {
        int v=g[u][i];
        par[v][0]=u;
        h[v]=h[u]+1;
        dfs(v);
    }
}
int minLabel(int u,int v) {
    return (lab[u]<lab[v]?u:v);
}
int maxLabel(int u,int v) {
    return (lab[u]>lab[v]?u:v);
}
void prepare(void) {
    dfs(1);
    FOR(i,1,n) minLab[i][0]=maxLab[i][0]=i;
    FOR(j,1,LOG) {
        FOR(i,1,n) par[i][j]=par[par[i][j-1]][j-1];
        FOR(i,1,n-MASK(j)+1) {
            minLab[i][j]=minLabel(minLab[i][j-1],minLab[i+MASK(j-1)][j-1]);
            maxLab[i][j]=maxLabel(maxLab[i][j-1],maxLab[i+MASK(j-1)][j-1]);
        }
    }
    FOR(i,1,n) {
        while (MASK(lg2[i])<=i) lg2[i]++;
        lg2[i]--;
    }
}
int getMinLabel(int l,int r) {
    int k=lg2[r-l+1];
    return (minLabel(minLab[l][k],minLab[r-MASK(k)+1][k]));
}
int getMaxLabel(int l,int r) {
    int k=lg2[r-l+1];
    return (maxLabel(maxLab[l][k],maxLab[r-MASK(k)+1][k]));
}
int LCA(int u,int v) {
    if (h[u]<h[v]) return (LCA(v,u));
    FORD(i,LOG,0) if (h[par[u][i]]>=h[v]) u=par[u][i];
    if (u==v) return (v);
    FORD(i,LOG,0) if (par[u][i]!=par[v][i]) {
        u=par[u][i];
        v=par[v][i];
    }
    return (par[u][0]);
}
void process(void) {
    REP(zz,q) {
        int u,v;
        scanf("%d%d",&u,&v);
        printf("%d\n",LCA(getMinLabel(u,v),getMaxLabel(u,v)));
    }
}
int main(void) {
    loadtree();
    prepare();
    process();
    return 0;
}