Хамгийн бага нийтлэг өвөг - Хоёртын өргөлт¶

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

Энэ өгүүлэлд тайлбарласан алгоритм модыг урьдчилан боловсруулахад $O(N \log N)$, дараа нь LCA асуулга бүрд $O(\log N)$ шаардана.

Алгоритм¶

Зангилаа бүрийн хувьд бид түүний дээрх өвөг, хоёр зангилаа дээрх өвөг, дөрөв дээрх өвөг гэх мэтийг урьдчилан тооцоолно. Тэдгээрийг up массивт хадгалъя, өөрөөр хэлбэл up[i][j] нь i=1...N, j=0...ceil(log(N))-ийн хувьд i зангилааны дээрх 2^j-р өвөг юм. Эдгээр мэдээлэл бидэнд дурын зангилаанаас түүний дээрх дурын өвөг рүү $O(\log N)$ хугацаанд үсрэх боломж олгоно. Бид энэ массивыг модны DFS тойролт ашиглан тооцоолж болно.

Зангилаа бүрийн хувьд бид мөн энэ зангилаад анх зочилсон хугацаа (өөрөөр хэлбэл DFS зангилааг олж илрүүлсэн хугацаа) ба түүнийг орхисон хугацааг (өөрөөр хэлбэл бүх хүүхдэд зочилж DFS функцээс гарсны дараах) санана. Бид энэ мэдээллийг ашиглан зангилаа нөгөө зангилааны өвөг эсэхийг тогтмол хугацаанд тодорхойлж болно.

Одоо бид (u, v) асуулга авлаа гэж үзье. Бид нэг зангилаа нөгөөгийнхөө өвөг эсэхийг шууд шалгаж болно. Энэ тохиолдолд энэ зангилаа аль хэдийн LCA болно. Хэрэв u нь v-ийн өвөг биш, v нь u-ийн өвөг биш бол бид v-ийн өвөг биш хамгийн өндөр (өөрөөр хэлбэл үндэст хамгийн ойр) зангилааг олох хүртэл u-ийн өвгүүдээр авирна (өөрөөр хэлбэл x нь v-ийн өвөг биш боловч up[x][0] нь өвөг байх x зангилаа). Бид энэ x зангилааг up массив ашиглан $O(\log N)$ хугацаанд олж болно.

Бид энэ үйл явцыг илүү нарийвчлан тайлбарлана. L = ceil(log(N)) байг. Эхлээд i = L гэж үзье. Хэрэв up[u][i] нь v-ийн өвөг биш бол бид u = up[u][i] гэж оноогоод i-г нэгээр багасгаж болно. Хэрэв up[u][i] нь өвөг бол бид зүгээр л i-г нэгээр багасгана. Сөрөг биш бүх i-ийн хувьд үүнийг хийсний дараа u зангилаа хайж буй зангилаа байх нь тодорхой — өөрөөр хэлбэл u нь v-ийн өвөг хэвээр биш боловч up[u][0] нь өвөг байна.

Одоо LCA-ийн хариулт нь up[u][0] буюу u зангилааны өвгүүдийн дундаас мөн v-ийн өвөг байх хамгийн бага зангилаа байх нь илэрхий.

Тиймээс LCA асуулгад хариулахдаа i-г ceil(log(N))-ээс 0 хүртэл тойрч, итерац бүрд нэг зангилаа нөгөөгийнхөө өвөг эсэхийг шалгана. Үүний үр дүнд асуулга бүрд $O(\log N)$-д хариулж болно.

Implementation¶

int n, l;
vector<vector<int>> adj;

int timer;
vector<int> tin, tout;
vector<vector<int>> up;

void dfs(int v, int p)
{
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i)
        up[v][i] = up[up[v][i-1]][i-1];

    for (int u : adj[v]) {
        if (u != p)
            dfs(u, v);
    }

    tout[v] = ++timer;
}

bool is_ancestor(int u, int v)
{
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int lca(int u, int v)
{
    if (is_ancestor(u, v))
        return u;
    if (is_ancestor(v, u))
        return v;
    for (int i = l; i >= 0; --i) {
        if (!is_ancestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void preprocess(int root) {
    tin.resize(n);
    tout.resize(n);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n, vector<int>(l + 1));
    dfs(root, root);
}

Хамгийн бага нийтлэг өвөг - Хоёртын өргөлт¶

Алгоритм¶

Implementation¶

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