4 ژوئیهٔ 2025

پایین‌ترین جد مشترک - صعود دودویی¶

فرض کنید $G$ یک درخت باشد. به ازای هر پرسش به شکل (u, v)، می‌خواهیم پایین‌ترین جد مشترک گره‌های u و v را پیدا کنیم. یعنی، می‌خواهیم گره w را پیدا کنیم که هم در مسیر u تا ریشه و هم در مسیر v تا ریشه قرار داشته باشد و اگر چندین گره با این ویژگی وجود داشت، آنی را انتخاب می‌کنیم که از ریشه دورتر است. به عبارت دیگر، گره مطلوب w، پایین‌ترین جد مشترک u و v است. به طور خاص، اگر u جد v باشد، آنگاه u پایین‌ترین جد مشترک آنهاست.

الگوریتم شرح داده شده در این مقاله برای پیش‌پردازش درخت به $O(N \log N)$ زمان و برای هر پرسش LCA به $O(\log N)$ زمان نیاز دارد.

الگوریتم¶

برای هر گره، جد یک پله بالاتر، جد دو پله بالاتر، جد چهار پله بالاتر و ... را پیش‌محاسبه می‌کنیم. این اطلاعات را در آرایه up ذخیره می‌کنیم؛ به طوری که up[i][j]، جد $2^j$-ام بالای گره i است (i=1...N, j=0...ceil(log(N))). این اطلاعات به ما امکان می‌دهد تا از هر گره به هر جد بالاتر از آن در زمان $O(\log N)$ بپریم. می‌توانیم این آرایه را با استفاده از یک پیمایش DFS روی درخت محاسبه کنیم.

برای هر گره، زمان اولین ملاقات (یعنی زمانی که DFS گره را کشف می‌کند) و زمان خروج از آن (یعنی پس از بازدید تمام فرزندان و خروج از تابع DFS) را نیز به خاطر می‌سپاریم. با استفاده از این اطلاعات، می‌توانیم در زمان ثابت تشخیص دهیم که آیا یک گره جد گره دیگری است یا خیر.

حال فرض کنید پرسش (u, v) را دریافت کرده‌ایم. می‌توانیم بلافاصله بررسی کنیم که آیا یکی از گره‌ها جد دیگری است یا خیر. در این صورت، آن گره همان LCA است. اگر u جد v نباشد و v نیز جد u نباشد، در میان اجداد u به سمت بالا حرکت می‌کنیم تا به بالاترین گره‌ای (یعنی نزدیک‌ترین به ریشه) برسیم که جد v نیست (یعنی گره x به طوری که x جد v نباشد، اما up[x][0] جد v باشد). می‌توانیم این گره x را در زمان $O(\log N)$ با استفاده از آرایه up پیدا کنیم.

این فرآیند را با جزئیات بیشتری شرح می‌دهیم. فرض کنید L = ceil(log(N)). ما i را از L به صورت نزولی تا 0 بررسی می‌کنیم. اگر up[u][i] جد v نباشد، u را برابر با up[u][i] قرار می‌دهیم. اگر up[u][i] یک جد باشد، u را تغییر نمی‌دهیم و به سراغ i بعدی می‌رویم. واضح است که پس از انجام این کار برای تمام مقادیر غیرمنفی i، گره u گره مطلوب خواهد بود - یعنی u هنوز جد v نیست، اما up[u][0] هست.

حالا، به وضوح، پاسخ LCA گره up[u][0] خواهد بود - یعنی، پایین‌ترین گره در میان اجداد گره u که جد v نیز هست.

بنابراین، پاسخ به یک پرسش LCA شامل یک حلقه از i = ceil(log(N)) تا 0 است که در هر تکرار، جد بودن یک گره نسبت به دیگری را بررسی می‌کند. در نتیجه، هر پرسش در زمان $O(\log N)$ پاسخ داده می‌شود.

پیاده‌سازی¶

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);
}

مسائل تمرینی¶

Contributors: