Хамгийн бага нийтлэг өвөг - $O(N)$ урьдчилсан боловсруулалттай $O(\sqrt{N})$ ба $O(\log N)$¶

Мод $G$ өгөгдсөн. $(v_1, v_2)$ хэлбэрийн асуулгууд өгөгдсөн бөгөөд асуулга бүрийн хувьд та хамгийн бага нийтлэг өвгийг (эсвэл хамгийн доод нийтлэг өвгийг) олох хэрэгтэй, өөрөөр хэлбэл үндэснээс $v_1$ хүрэх зам болон үндэснээс $v_2$ хүрэх зам дээр орших ба хамгийн доод нь байх орой $v$-г олно. Өөрөөр хэлбэл хайж буй орой $v$ нь $v_1$ ба $v_2$-ийн хамгийн доод өвөг юм. Тэдгээрийн хамгийн бага нийтлэг өвөг нь $v_1$ ба $v_2$-ийн хоорондох хамгийн богино зам дээр оршдог нь илэрхий. Мөн хэрэв $v_1$ нь $v_2$-ийн өвөг бол $v_1$ нь тэдгээрийн хамгийн бага нийтлэг өвөг юм.

Алгоритмын санаа¶

Асуулгад хариулахын өмнө бид модыг урьдчилан боловсруулах хэрэгтэй. Бид үндэснээс эхлэн DFS тойролт хийж, зочилсон оройнуудынхаа дарааллыг хадгалах $\text{euler}$ жагсаалтыг байгуулна (орой анх зочлох үед, мөн DFS тойролт түүний хүүхдүүдээс буцаж ирсний дараа жагсаалтад нэмэгдэнэ). Үүнийг мөн модны Эйлерийн тойролт гэж нэрлэдэг. Энэ жагсаалтын хэмжээ $O(N)$ байх нь тодорхой. Мөн бид орой $i$ бүрийн хувьд $\text{euler}$ дэх түүний анхны орцыг хадгалах $\text{first}[0..N-1]$ массивыг байгуулах хэрэгтэй. Өөрөөр хэлбэл $\text{euler}[\text{first}[i]] = i$ байх $\text{euler}$ дэх анхны байрлал. Мөн DFS ашиглан бид зангилаа бүрийн өндрийг (үндэснээс түүн хүртэлх зай) олж $\text{height}[0..N-1]$ массивт хадгалж болно.

Тэгвэл бид Эйлерийн тойролт ба нэмэлт хоёр массивыг ашиглан асуулгад хэрхэн хариулах вэ? Асуулга нь $v_1$ ба $v_2$-ийн хос гэж үзье. Эйлерийн тойролтод $v_1$-д анх зочлох ба $v_2$-д анх зочлохын хооронд зочилсон оройнуудыг авч үзье. Энэ зам дээрх хамгийн бага өндөртэй орой нь $\text{LCA}(v_1, v_2)$ болохыг харахад амархан. LCA нь $v_1$ ба $v_2$-ийн хоорондох хамгийн богино замын хэсэг байх ёстойг бид аль хэдийн анзаарсан. Энэ нь мөн хамгийн бага өндөртэй орой байх ёстой нь тодорхой. Мөн Эйлерийн тойролтод бид үндсэндээ хамгийн богино замыг ашигладаг, зөвхөн зам дээр тааралдсан бүх дэд модод нэмж зочилдгоос бусад тохиолдолд. Гэвч эдгээр дэд модны бүх орой модонд LCA-аас доогуур байх тул илүү их өндөртэй байна. Тиймээс $\text{LCA}(v_1, v_2)$-г $\text{first}(v_1)$ ба $\text{first}(v_2)$-ийн хоорондох Эйлерийн тойролтод хамгийн бага өндөртэй оройг олох замаар давтагдашгүйгээр тодорхойлж болно.

Энэ санааг зураглан үзүүлье. Дараах граф ба харгалзах өндөртэй Эйлерийн тойролтыг авч үзье:

$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Оройнууд:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ \hline \text{Өндөр:} & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline \end{array}$$

Орой $6$-аас эхэлж $4$-д төгсөх тойролтод бид $[6, 2, 1, 3, 1, 4]$ оройнуудад зочилно. Эдгээр оройн дотроос орой $1$ хамгийн бага өндөртэй тул $\text{LCA(6, 4) = 1}$ болно.

Товчлон дүгнэвэл: асуулгад хариулахын тулд бид $\text{euler}$ массивын $\text{first}[v_1]$-ээс $\text{first}[v_2]$ хүртэлх мужид хамгийн бага өндөртэй оройг олох л хэрэгтэй. Ингэснээр LCA бодлого RMQ бодлого болж буурна (интервал дахь хамгийн бага элементийг олох бодлого).

Квадрат язгуурын задаргаа ашиглан $O(N)$ хугацаанд урьдчилан боловсруулж, асуулга бүрд $O(\sqrt{N})$-д хариулах шийдлийг олж болно.

Хэрчмийн мод ашиглан $O(N)$ хугацаанд урьдчилан боловсруулж, асуулга бүрд $O(\log N)$-д хариулж болно.

Хадгалагдсан утгууд бараг хэзээ ч шинэчлэгдэхгүй тул Сийрэг хүснэгт илүү сайн сонголт байж болох ба энэ нь $O(N\log N)$ байгуулах хугацаатайгаар $O(1)$-д асуулгад хариулах боломж олгоно.

Implementation¶

In the following implementation of the LCA algorithm a Segment Tree is used.

struct LCA {
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
    int n;

    LCA(vector<vector<int>> &adj, int root = 0) {
        n = adj.size();
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        visited.assign(n, false);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }

    void dfs(vector<vector<int>> &adj, int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node]) {
            if (!visited[to]) {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
    }

    void build(int node, int b, int e) {
        if (b == e) {
            segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }

    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;

        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }

    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};

Хамгийн бага нийтлэг өвөг - $O(N)$ урьдчилсан боловсруулалттай $O(\sqrt{N})$ ба $O(\log N)$¶

Алгоритмын санаа¶

Implementation¶

Дасгал бодлогууд¶