Lowest Common Ancestor (LCA) - বাইনারি লিফটিং#

ধরি $G$ একটি ট্রি। প্রতিটি (u, v) আকারের কুয়েরির জন্য আমরা u এবং v নোডের LCA বের করতে চাই, অর্থাৎ আমরা এমন একটি নোড w খুঁজতে চাই যেটি u থেকে রুট নোড পর্যন্ত পাথে অবস্থিত, v থেকে রুট নোড পর্যন্ত পাথেও অবস্থিত, এবং একাধিক এরকম নোড থাকলে আমরা রুট নোড থেকে সবচেয়ে দূরেরটি বেছে নিই। অন্যভাবে বলতে গেলে, কাঙ্ক্ষিত নোড w হলো u এবং v-এর সবচেয়ে নিচের অ্যানসেস্টর। বিশেষত, যদি u হয় v-এর অ্যানসেস্টর, তাহলে u হলো তাদের LCA।

এই আর্টিকেলে বর্ণিত অ্যালগরিদমের ট্রি প্রিপ্রসেসিং-এর জন্য $O(N \log N)$ এবং প্রতিটি LCA কুয়েরির জন্য $O(\log N)$ সময় লাগবে।

অ্যালগরিদম#

প্রতিটি নোডের জন্য আমরা প্রিকম্পিউট করব তার ঠিক উপরের অ্যানসেস্টর, দুই নোড উপরের অ্যানসেস্টর, চার নোড উপরের অ্যানসেস্টর ইত্যাদি। এগুলো up অ্যারেতে সংরক্ষণ করা যাক, অর্থাৎ up[i][j] হলো i নোডের 2^j-তম উপরের অ্যানসেস্টর, যেখানে 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] হলো)। আমরা up অ্যারে ব্যবহার করে $O(\log N)$ সময়ে এই নোড x খুঁজে পেতে পারি।

চলো এই প্রক্রিয়াটি আরো বিস্তারিতভাবে দেখি। ধরি 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)$-এ উত্তর দেওয়া যায়।

ইমপ্লিমেন্টেশন#

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

অনুশীলন সমস্যা#