محاسبه‌ی پایین‌ترین جد مشترک

در نظریه گراف و علوم‌کامپیوتر پایین‌ترین جد مشترک برای دو راس مثل $u$ و $v$ در هر درخت ریشه دار پایین‌ترین راسی است که هر دوی $u$ و $v$ در زیر درخت آن باشند . درخت $n$ راسی ریشه‌دار $T$ و $m$ پرسش به صورت $(u_i, v_i)$ به طوری که $u_i$ و $v_i$ راس‌هایی از $T$ هستند داده‌شده است. مسئله پیدا کردن پایین‌ترین جد مشترک برای هر دو راس $v_i$ و $u_i$ است.
مثلا در شکل زیر راس $4$ پایین‌ترین جد مشترک راس‌های $10$ و $8$ است.

ساده‌ترین راهی که به ذهن میرسد این است که به ازای هر پرسش $(u_i, v_i)$، ابتدا راسی که در عمق پایین‌تری وجود دارد را تا جایی که عمق آن برابر با عمق راس دیگر شود بالا بیاوریم(یعنی $ u = father[u] $).

سپس تا زمانی که دو راس برابر نشدند در هر مرحله هر دو را یکی بالا میاوریم. از آنجایی که راس ریشه جد مشترک آن‌هاست این فرایند حتما متوقف می‌شود و راسی که در آن متوقف شدیم پایین‌ترین راسی‌است که جد مشترک $u_i$ و $ v_i$ است. این الگوریتم اولیه از مرتبه‌ی $O(n)$ برای هر پرسش عمل می‌کند و هزینه کل از مرتبه‌ی $ O(n * m)$ خواهد بود. (چرا؟)

ایده‌ایی که برای بهبود عملکرد این الگوریتم به ذهن می‌رسد استفاده از روشی است که i-امین راس بالای هر راس دلخواه را در مرتبه‌ی خوبی در اختیار ما قرار بدهد. مقدار $ancestor[v][i]$ را برابر با $2^i$-امین راس بالای راس v در نظر می‌گیریم. برای تعیین مقادیر آرایه ancestor از روش برنامه‌ریزی پویا استفاده می‌کنیم:

• به ازای هر v و i = 0 مقدار $ancestor[v][i] = father[v]$ است.
• به ازای هر i ناصفر $ancestor[v][i] = ancestor[ ancestor[v][i-1] ] [i-1]$ است.

در قسمت اول الگوریتم ابتدا لازم بود که v و u را هم ارتفاع کنیم، می‌توانیم برای پیدا کردن x-امین راس بالای v با گام‌های به اندازه‌ی $2^i$ بالا برویم و در $O(lgn)$ مرحله راس مورد نظر را پیدا کنیم. (چرا؟) در قسمت بعدی برای پیدا کردن پایین‌ترین جد مشترک u و v می‌توانیم با جستجوی‌دودویی روی فاصله‌ی راس جواب و v جواب را در مرتبه‌ی $O(lg^2 n )$ پیدا کنیم. می‌توانیم با کمی هوشمندی مرتبه‌ی پیدا کردن جواب برای هر پرسش را از $O(lg n+ lg^2 n) = O(lg^2 n)$ به $O(lgn)$ کاهش دهیم. (راهنمایی: نمایش دودویی هر عدد کوچک‌تر از n حداکثر $lg n$ رقم دارد).

LCA.cpp

#include <iostream>
#include <vector>
 
using namespace std;
 
const int MAXN = 100 * 1000 + 1;
const int MAX_LG_N = 17 + 1;
const int MAXM = 100 * 1000;
 
int ancestor[MAXN][MAX_LG_N];
int father[MAXN];
int n, m; 
int query[MAXM][2];
int answer[MAXM];
int depth[MAXN];
vector<int> child[MAXN];
bool dfs_mark[MAXN];
 
void dfs(int v);
int up(int v, int dist);
void input();
void preprocess();
int calculate_lca(int v, int u);
 
int main(){
    // get tree from input
    cin >> n;
    for(int i = 2; i <= n; i++){
        cin >> father[i];
        child[ father[i] ].push_back(i);
    }
    for(int i = 1; i <= m; i++)
        cin >> query[i][0] >> query[i][1];
 
    preprocess();
 
    // get queries form input and print answers
    cin >> m;
    for(int i = 1; i <= m; i++){
        int v, u;
        cin >> v >> u;
        cout << calculate_lca(v, u) << endl;
    }
    return 0;
}
 
void preprocess(){
    // calculate ancestor[v][i]
    father[1] = 1; // father[root] = root
    for(int i = 1; i <= n; i++)
        ancestor[i][0] = father[i];
    for(int j = 1; j < MAX_LG_N; j++)
        for(int i = 1; i <= n; i++)
            ancestor[i][j] = ancestor[ ancestor[i][j-1] ][j-1];
 
    // calculate depth[v] 
    dfs(1); // dfs(root)
}
 
int calculate_lca(int v, int u){
    if(depth[v] > depth[u]) 
        swap(u, v); // to sure depth[v] < depth[u]
    u = up(u, depth[u] - depth[v]);
    for(int j = MAX_LG_N - 1; j >= 0; j--)
        if(ancestor[u][j] != ancestor[v][j]){
            u = ancestor[u][j];
            v = ancestor[v][j];
        }
    if(u == v) 
        return v;
    return ancestor[v][0];
}
 
 
void dfs(int v){
    dfs_mark[v] = true;
    for(int i = 0; i < child[v].size(); i++){
        int u = child[v][i];
        if(!dfs_mark[u]){
            depth[u] = depth[v] + 1;
            dfs(u);
        }
    }
}
 
int up(int v, int dist){
    for(int i = MAX_LG_N - 1; i >= 0; i--)
        if(dist >= (1 << i)){
            v = ancestor[v][i];
            dist -= (1 << i);
        }
    return v;
}

• superviva [سطح: متوسط]

• پایین‌ترین جد مشترک - ویکی‌پدیا