Tree-এর কৌশল — LCA, binary lifting আর diameter

১ · সমস্যা — বংশতালিকায় “সবচেয়ে কাছের সাধারণ পূর্বপুরুষ”

ঈদের দাওয়াতে দুই অপরিচিত তরুণের দেখা। আলাপে জানা গেল দুজনেই একই বড় পরিবারের — কিন্তু সম্পর্কটা ঠিক কী? চাচাতো ভাই, নাকি দাদার ভাইয়ের নাতি? উত্তর বের করার উপায় একটিই: দুজনের বংশধারা ধরে ওপরে উঠতে থাকুন, যতক্ষণ না দুই ধারা প্রথমবার একই মানুষে মেলে। সেই মানুষটিই দুজনের সবচেয়ে কাছের সাধারণ পূর্বপুরুষ. তিনি দুজনের দাদা হলে তাঁরা চাচাতো/ফুপাতো ভাই; পরদাদা হলে সম্পর্ক আরও দূরের।

একটি অফিসেও একই প্রশ্ন ওঠে। একটি বড় কোম্পানির ক্রমবিন্যাসে (পর্ব ২৬) দুজন কর্মীর মধ্যে বিরোধ হলে কোন কর্মকর্তা সিদ্ধান্ত দেবেন? যিনি দুজনেরই ঊর্ধ্বতন, আর এমনদের মধ্যে সবচেয়ে নিচের পদে — কারণ তাঁর চেয়ে ওপরে যাওয়ার দরকার নেই। কম্পিউটারে ফোল্ডারের ক্ষেত্রেও: D:\office\hr\2026 থেকে D:\office\accounts-এ যেতে প্রথমে দুই ঠিকানার শেষ সাধারণ ফোল্ডার office পর্যন্ত উঠতে হয়, তারপর নামতে হয়।

Tree-র ভাষায় (পর্ব ২৬): একটি rooted tree-তে দুটি node u আর v-এর lowest common ancestor (LCA) হলো সেই node, যে দুজনেরই ancestor (একজন নিজেও হতে পারে) আর এমন node-দের মধ্যে root থেকে সবচেয়ে দূরে, অর্থাৎ সবচেয়ে গভীর। পর্ব ২৬-এ binary tree-তে প্রতি প্রশ্নে O(n)-এর একটি recursive সমাধান দেখেছিলেন। কিন্তু প্রশ্ন যদি হয় ২ লাখ node-এর tree-তে ২ লাখ প্রশ্ন? এই পর্বের মূল প্রশ্ন এটিই — একবার প্রস্তুতি নিয়ে প্রতিটি প্রশ্নের দ্রুত উত্তর। পুরো পর্ব জুড়ে নিচের tree-টি আমাদের সঙ্গী:

            1             depth 0
          /   \
         2     3          depth 1
        / \    │
       4   5   6          depth 2
      / \      │
     7   8     9          depth 3
     │         │
    10        11          depth 4
     │         │
    12        13          depth 5

LCA জানলে আরও অনেক প্রশ্নের উত্তর বের হয়: দুই node-এর দূরত্ব, তাদের মাঝের পথে সবচেয়ে ধীর লিংক, একটি node আরেকটির পূর্বপুরুষ কি না। আর এই পর্বের শেষ অংশে দেখবেন আরেকটি ক্লাসিক প্রশ্ন — tree diameter, অর্থাৎ tree-র সবচেয়ে লম্বা পথ, যা পর্ব ২৬-এ binary tree-তে দেখেছিলেন; এখানে যেকোনো tree-তে, দুইবার BFS দিয়ে।

২ · Edge-তালিকা থেকে rooted tree — BFS দিয়ে parent আর depth

কনটেস্টে বা বাস্তব ডেটায় tree প্রায় কখনো “এর বাঁ সন্তান, ওর ডান সন্তান” আকারে আসে না। আসে এভাবে: “n টি শহর, n − 1 টি রাস্তা; প্রতিটি লাইনে দুটি শহর a b, যাদের মাঝে রাস্তা আছে।” রাস্তাগুলোর কোনো দিক নেই — এটি একটি undirected graph, যা connected আর চক্রহীন, অর্থাৎ একটি tree. এখানে কে parent আর কে সন্তান, তা ঠিক করে দেওয়া নেই। আমাদের কাজ একটি node-কে root বেছে tree-টিকে “ঝুলিয়ে” দেওয়া — তখন সেটি হয় একটি rooted tree.

প্রথমে প্রতিটি node-এর প্রতিবেশীদের একটি তালিকা বানান — adjacency list (পর্ব ৩৯-এ বিস্তারিত)। প্রতিটি edge (a, b)-র জন্য a-এর তালিকায় b আর b-এর তালিকায় a. প্রধান উদাহরণের edge-তালিকা আর তা থেকে পাওয়া কয়েকটি তালিকা:

edges: 1-2 1-3 2-4 2-5 3-6 4-7 4-8 6-9 7-10 9-11 10-12 11-13
adj[1] = 2 3      adj[2] = 1 4 5      adj[4] = 2 7 8      adj[12] = 10

তারপর root (এখানে 1) থেকে একটি BFS (পর্ব ৪০) চালান। যে node থেকে একটি নতুন node প্রথম আবিষ্কৃত হলো, সে-ই তার parent, আর নতুনটির depth = parent-এর depth + 1. আগে দেখা প্রতিবেশী (যেমন parent নিজে) বাদ — তাই দিকহীন edge-ও দুবার গোনা হয় না। নিচের ডায়াগ্রামে দেখুন queue কীভাবে স্তরে স্তরে tree খুলে দেয়:

BFS-এর বদলে DFS (পর্ব ৪১) দিয়েও একই কাজ হয়: dfs(v, p)-এ প্রতিটি প্রতিবেশী u ≠ p-এর জন্য par[u] = v, depth[u] = depth[v] + 1, তারপর dfs(u, v). DFS-এর বাড়তি লাভ হলো ঢোকা-বেরোনোর সময় (অংশ ৮) একই হাঁটায় পাওয়া যায়। কিন্তু সাবধান: ২ লাখ node-এর শিকলের মতো tree-তে recursive DFS-এর recursion depth ২ লাখ — Python-এ নিশ্চিত RecursionError, C++-এ stack overflow-এর ঝুঁকি (পর্ব ০৭, ২৬). BFS নিজের queue ব্যবহার করে বলে এই ভয় নেই — এজন্যই এই পর্বের কোডে BFS.

৩ · সরল LCA — এক ধাপ এক ধাপ করে ওপরে ওঠা

parent আর depth হাতে থাকলে বংশতালিকার পদ্ধতিটি সরাসরি কোডে আসে, দুই ধাপে:

1. সমান গভীরতায় আনা. যে বেশি গভীরে, তাকে এক এক ধাপ ওপরে তুলুন (u = par[u]), যতক্ষণ না দুজনের depth সমান হয়।
2. একসাথে ওঠা. এখন দুজন একই level-এ। যতক্ষণ u ≠ v, দুজনকেই একসাথে এক ধাপ ওপরে তুলুন। যেখানে প্রথম মেলে, সেটিই LCA.

উদাহরণ LCA(12, 8): depth 5 আর 3. 12 দুই ধাপ উঠে 12 → 10 → 7. এখন 7 আর 8, দুজনেই depth 3, কিন্তু আলাদা। একসাথে এক ধাপ: 7 → 4, 8 → 4 — মিলে গেল, LCA = 4. প্রথম ধাপটি জরুরি কেন? সমান গভীরতায় না এনে একসাথে উঠলে 12 আর 8 কখনো একই সময়ে 4-এ পৌঁছাবে না — 8 পৌঁছাবে এক ধাপে, 12 তিন ধাপে।

কেন ঠিক. দ্বিতীয় ধাপের শুরুতে u আর v একই depth-এ। দুজনের পূর্বপুরুষদের মধ্যে একই depth-এ বড়জোর একজন করে থাকে, তাই দুজনকে সমান হারে তুললে তারা সব সময় একই depth-এ থাকে, আর প্রথম যে depth-এ দুজনের পূর্বপুরুষ একই node, সেটিই সবচেয়ে গভীর সাধারণ পূর্বপুরুষ। একবার মিললে তার ওপরে সবাই সাধারণ — কিন্তু তারা কম গভীর।

খরচ. প্রতি প্রশ্নে বড়জোর depth[u] + depth[v] ধাপ, অর্থাৎ O(h), যেখানে h হলো tree-র উচ্চতা। ভারসাম্যপূর্ণ tree-তে h ≈ log n — চমৎকার। কিন্তু বাস্তব আর কনটেস্টের tree প্রায়ই লম্বা শিকলের মতো: h = n − 1. তখন q টি প্রশ্নে O(n·q). n = q = 2·10⁵ হলে প্রায় 4·10¹⁰ ধাপ — কয়েক মিনিট, অথচ সময়সীমা সাধারণত ১–২ সেকেন্ড। এই সরল পদ্ধতি তবু ফেলনা নয়: অংশ ৫-এর প্রোগ্রামে এটিই দ্রুত পদ্ধতির উত্তর যাচাইয়ের brute force.

৪ · Binary lifting-এর টেবিল — up[k][v] = 2^k-তম পূর্বপুরুষ

প্রতিটি node v-এর জন্য আগে থেকে জমিয়ে রাখুন: up[k][v] = v থেকে 2^k ধাপ ওপরের পূর্বপুরুষ. up[0][v] হলো parent, up[1][v] দাদা (২ ধাপ), up[2][v] ৪ ধাপ ওপরের পূর্বপুরুষ, ইত্যাদি। পুরো টেবিল বানানোর চাবি একটি পর্যবেক্ষণ: 2^k ধাপ = প্রথমে 2^k−1 ধাপ, তারপর আবার 2^k−1 ধাপ। তাই

পর্ব ৩৭-এর sparse table-এর সাথে মিলটা লক্ষ করুন: সেখানে দৈর্ঘ্য 2^k-এর ব্লকের উত্তর বানানো হতো দৈর্ঘ্য 2^k−1-এর দুটি ব্লক জুড়ে; এখানে 2^k ধাপের লাফ বানানো হয় 2^k−1-এর দুটি লাফ জুড়ে। একই “দ্বিগুণ করা” (doubling) কৌশল। root-এর ওপরে লাফ দিলে? আমরা par[root] = root রেখেছি, তাই অতিরিক্ত লাফ root-এ আটকে যায় — কোনো সীমানা-পরীক্ষা লাগে না।

LOG কত সারি? দরকার এমন LOG, যাতে 2^LOG যেকোনো depth-এর চেয়ে বড় হয়; depth বড়জোর n − 1, তাই 2^LOG > n যথেষ্ট — n = 13-এর জন্য LOG = 4 (2⁴ = 16), n = 2·10⁵-এর জন্য 18. প্রধান উদাহরণে টেবিলটি সারি ধরে বানানো দেখুন:

খরচ. টেবিলে LOG × (n + 1) টি ঘর, LOG = ⌈log₂(n + 1)⌉-এর কাছাকাছি, আর প্রতিটি ঘর O(1)-এ ভরে — সময় ও জায়গা দুটোই Θ(n log n). সারি k বানাতে সারি k − 1 সম্পূর্ণ থাকা চাই, তাই বাইরের লুপ k-এর ওপর, ভেতরের লুপ v-এর ওপর। (উল্টো ক্রমে লিখলে up[k − 1]-এর কিছু ঘর তখনো খালি থাকতে পারে — খুব প্রচলিত বাগ। তবে BFS ক্রমে v সাজিয়ে প্রতিটি v-এর পুরো কলাম একসাথে ভরলেও ঠিক থাকে, কারণ তখন সব পূর্বপুরুষের কলাম আগেই ভরা।)

k-তম পূর্বপুরুষ-এর প্রশ্ন, যেমন “এই কর্মীর ৫ ধাপ ওপরের কর্মকর্তা কে?”, এখন সরাসরি: k-এর প্রতিটি চালু bit j-এর জন্য একটি 2^j লাফ — পর্ব ০৭-এর binary exponentiation-এর মতোই bit ধরে ধরে কাজ। k > depth[v] হলে এমন পূর্বপুরুষ নেই। মোট O(log n):

int kth(int v, int k) {                    // k-th ancestor of v, or -1 if it does not exist
    if (k > depth[v]) return -1;
    for (int j = 0; j < LOG; ++j)
        if ((k >> j) & 1) v = up[j][v];     // bit j of k is set: jump 2^j levels
    return v;
}

৫ · Binary lifting দিয়ে LCA — সমান গভীরতা, তারপর দুজনের একসাথে লাফ

অংশ ৩-এর সরল পদ্ধতির দুটি ধাপই এখন লাফে করা যায়:

1. সমান গভীরতা. ধরুন depth[u] ≥ depth[v] (না হলে দুটি অদলবদল)। u-কে ঠিক d = depth[u] − depth[v] ধাপ তুলুন — এটি তো k-তম পূর্বপুরুষের প্রশ্নই। এরপর u = v হলে v নিজেই LCA.
2. দুজনের একসাথে লাফ. k = LOG − 1 থেকে 0 পর্যন্ত, বড় লাফ আগে: যদি up[k][u] ≠ up[k][v], দুজনকেই লাফ দিন। সমান হলে লাফ দেবেন না — কারণ সেই node একটি সাধারণ পূর্বপুরুষ, কিন্তু হয়তো LCA-র ওপরে। শেষে u আর v ঠিক LCA-র ঠিক নিচের দুই সন্তান, তাই উত্তর up[0][u].

Pseudocode — LCA by binary lifting (nodes 1..n, up[k][root] = root)

lca(u, v):
    if depth[u] < depth[v]: swap(u, v)
    for k = LOG-1 down to 0:                  // phase 1: lift u to v's depth
        if depth[u] - 2^k >= depth[v]: u = up[k][u]
    if u == v: return u
    for k = LOG-1 down to 0:                  // phase 2: lift both, never onto a common ancestor
        if up[k][u] != up[k][v]:
            u = up[k][u];  v = up[k][v]
    return up[0][u]

সবচেয়ে শিক্ষণীয় প্রশ্ন LCA(12, 11) — এখানে দুই ধাপেই আসল লাফ আছে:

কেন ঠিক — একটি invariant আর binary search. দ্বিতীয় phase-এ একটি কথা সব সময় সত্য: “u আর v একই depth-এ, আলাদা node, আর LCA দুজনেরই কঠোরভাবে ওপরে।” শুরুতে সত্য (u ≠ v). লাফ দিই শুধু তখন, যখন up[k][u] ≠ up[k][v] — তখন নতুন u, v-ও আলাদা, তাই LCA তখনো ওপরে; invariant টিকে থাকে। এখন ভাবুন t = depth[u] − depth[LCA] − 1, অর্থাৎ “LCA-র ঠিক নিচে পৌঁছাতে কত ধাপ লাগবে”. j ধাপ ওপরের পূর্বপুরুষ দুজনের আলাদা হয় ঠিক তখন, যখন j ≤ t — এটি একটি monotonic predicate (পর্ব ১৯): ছোট j-এ সত্য, একটি সীমার পর চিরকাল মিথ্যা। বড় থেকে ছোট 2^k চেষ্টা করে “সত্য থাকলে লাফ” দেওয়া মানে t-এর binary রূপ ওপরের bit থেকে একটি একটি করে বের করা — পর্ব ১৮-এর binary search, শুধু ধাপের দৈর্ঘ্য দুইয়ের ঘাতে। t < 2^LOG বলে প্রতিটি bit একবারই দেখা যথেষ্ট, আর শেষে মোট ঠিক t ধাপ ওঠা হয়: u আর v LCA-র ঠিক নিচে, তাই up[0][u] = LCA. ∎

খরচ. দুই phase-এ LOG টি করে পরীক্ষা, প্রতিটি O(1) — প্রতি প্রশ্নে O(log n). প্রস্তুতি O(n log n). n = q = 2·10⁵-এ মোট কাজ প্রায় 2·10⁵ × 36 ≈ 7·10⁶ ধাপ — অংশ ৩-এর 4·10¹⁰-এর তুলনায় কয়েক হাজার গুণ কম।

দুই node-এর দূরত্ব

u থেকে v-এর পথ সব সময় LCA দিয়ে যায়: u থেকে LCA পর্যন্ত ওঠা, তারপর v পর্যন্ত নামা। প্রথম অংশে depth[u] − depth[w] টি edge, দ্বিতীয় অংশে depth[v] − depth[w] টি (w = LCA). যোগ করলে:

নিচের প্রোগ্রাম প্রধান উদাহরণের edge-তালিকা থেকে tree ঝুলিয়ে up টেবিল বানায়, কয়েকটি প্রশ্নের LCA আর দূরত্ব ছাপে, তারপর সব ১৩ × ১৩ = ১৬৯টি জোড়ায় binary lifting-এর উত্তর অংশ ৩-এর সরল পদ্ধতির সাথে মিলিয়ে দেখে — ছোট আকারের stress testing.

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
int main() {
    const int n = 13, LOG = 4;                                  // 2^LOG > n
    vector<pair<int, int>> edges{{1,2},{1,3},{2,4},{2,5},{3,6},{4,7},{4,8},{6,9},{7,10},{9,11},{10,12},{11,13}};
    vector<vector<int>> adj(n + 1), up(LOG, vector<int>(n + 1));
    for (auto [a, b] : edges) { adj[a].push_back(b); adj[b].push_back(a); }
    vector<int> depth(n + 1, -1); depth[1] = 0; up[0][1] = 1;   // root's parent = itself
    queue<int> q; q.push(1);
    while (!q.empty()) {                                        // BFS from the root: parent and depth
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (depth[v] < 0) { depth[v] = depth[u] + 1; up[0][v] = u; q.push(v); }
    }
    for (int k = 1; k < LOG; ++k)
        for (int v = 1; v <= n; ++v) up[k][v] = up[k - 1][up[k - 1][v]];   // 2^k = 2^(k-1) + 2^(k-1)
    auto lca = [&](int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        for (int k = LOG - 1; k >= 0; --k)                      // lift u to v's depth
            if (depth[u] - (1 << k) >= depth[v]) u = up[k][u];
        if (u == v) return u;
        for (int k = LOG - 1; k >= 0; --k)                      // lift both, staying below the LCA
            if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
        return up[0][u];
    };
    auto naive = [&](int u, int v) {                            // walk up one edge at a time
        while (depth[u] > depth[v]) u = up[0][u];
        while (depth[v] > depth[u]) v = up[0][v];
        while (u != v) { u = up[0][u]; v = up[0][v]; }
        return u;
    };
    for (auto [u, v] : vector<pair<int, int>>{{12, 8}, {12, 11}, {10, 5}, {4, 12}, {13, 9}}) {
        int w = lca(u, v);
        cout << "lca(" << u << "," << v << ") = " << w << "  dist = " << depth[u] + depth[v] - 2 * depth[w] << '\n';
    }
    int bad = 0;
    for (int u = 1; u <= n; ++u) for (int v = 1; v <= n; ++v) bad += lca(u, v) != naive(u, v);
    cout << "all " << n * n << " pairs checked, mismatches: " << bad << '\n';
}

lca(12,8) = 4  dist = 4
lca(12,11) = 1  dist = 9
lca(10,5) = 2  dist = 4
lca(4,12) = 4  dist = 3
lca(13,9) = 9  dist = 2
all 169 pairs checked, mismatches: 0

from collections import deque

n, LOG = 13, 4                                   # 2**LOG > n
edges = [(1,2),(1,3),(2,4),(2,5),(3,6),(4,7),(4,8),(6,9),(7,10),(9,11),(10,12),(11,13)]
adj = [[] for _ in range(n + 1)]
for a, b in edges:
    adj[a].append(b); adj[b].append(a)
depth = [-1] * (n + 1); depth[1] = 0
up = [[0] * (n + 1) for _ in range(LOG)]; up[0][1] = 1   # root's parent = itself
q = deque([1])
while q:                                         # BFS from the root: parent and depth
    u = q.popleft()
    for v in adj[u]:
        if depth[v] < 0:
            depth[v] = depth[u] + 1; up[0][v] = u; q.append(v)
for k in range(1, LOG):
    for v in range(1, n + 1):
        up[k][v] = up[k - 1][up[k - 1][v]]       # 2^k = 2^(k-1) + 2^(k-1)

def lca(u, v):
    if depth[u] < depth[v]: u, v = v, u
    for k in reversed(range(LOG)):               # lift u to v's depth
        if depth[u] - (1 << k) >= depth[v]: u = up[k][u]
    if u == v: return u
    for k in reversed(range(LOG)):               # lift both, staying below the LCA
        if up[k][u] != up[k][v]: u, v = up[k][u], up[k][v]
    return up[0][u]

def naive(u, v):                                 # walk up one edge at a time
    while depth[u] > depth[v]: u = up[0][u]
    while depth[v] > depth[u]: v = up[0][v]
    while u != v: u, v = up[0][u], up[0][v]
    return u

for u, v in [(12, 8), (12, 11), (10, 5), (4, 12), (13, 9)]:
    w = lca(u, v)
    print(f"lca({u},{v}) = {w}  dist = {depth[u] + depth[v] - 2 * depth[w]}")
bad = sum(lca(u, v) != naive(u, v) for u in range(1, n + 1) for v in range(1, n + 1))
print(f"all {n * n} pairs checked, mismatches: {bad}")

lca(12,8) = 4  dist = 4
lca(12,11) = 1  dist = 9
lca(10,5) = 2  dist = 4
lca(4,12) = 4  dist = 3
lca(13,9) = 9  dist = 2
all 169 pairs checked, mismatches: 0

৬ · পথের ওপর হিসাব — ওজনসহ দূরত্ব, সবচেয়ে ধীর লিংক

বাস্তবের tree-তে edge-এর সাধারণত একটি ওজন থাকে। একটি প্রতিষ্ঠানের নেটওয়ার্ক ভাবুন, যেখানে router-গুলো একটি tree আকারে যুক্ত (অনেক নেটওয়ার্কে লুপ ঠেকাতে লিংকগুলোকে ইচ্ছা করেই একটি tree-তে নামানো হয়)। প্রতিটি লিংকের একটি latency আছে — মিলিসেকেন্ডে কত দেরি হয়। দুই router-এর মাঝে প্যাকেট কত দেরিতে পৌঁছাবে? এটি একটি weighted tree-তে দূরত্বের প্রশ্ন।

ওজনসহ দূরত্ব. BFS-এর সময় depth-এর পাশাপাশি rootDist[v] = root থেকে v পর্যন্ত ওজনের যোগফল রাখুন (rootDist[সন্তান] = rootDist[parent] + edge-এর ওজন)। তারপর ঠিক আগের যুক্তিতে: dist(u, v) = rootDist[u] + rootDist[v] − 2·rootDist[w], w = LCA(u, v). LCA বের করতে ওজন লাগে না — শুধু depth (edge-সংখ্যা) দিয়েই lifting চলে। এটি আসলে পর্ব ১৭-এর prefix sum-এর tree সংস্করণ: অ্যারেতে sum(l..r) = P[r] − P[l − 1]; tree-তে root থেকে prefix, আর LCA হলো “বিয়োগের বিন্দু”.

পথের সর্বোচ্চ বা সর্বনিম্ন. “দুই router-এর পথে সবচেয়ে ধীর লিংক কোনটি?” — যোগফলের মতো বিয়োগ করে এটি পাওয়া যায় না, কারণ max-এর কোনো উল্টো কাজ নেই। সমাধান: up টেবিলের পাশে আরেকটি টেবিল রাখুন, যেখানে প্রতিটি লাফের সাথে সেই লাফে পার হওয়া edge-গুলোর সর্বোচ্চ জমা থাকে।

Pseudocode — maximum edge weight on a path (w(v) = weight of edge v–parent(v))

mx[0][v] = w(v)                                       // the single edge above v
mx[k][v] = max( mx[k-1][v], mx[k-1][ up[k-1][v] ] )   // first half of the jump, then second half

pathMax(u, v):  best = -infinity
    run lca(u, v); before EVERY jump of u:  best = max(best, mx[k][u]);  same for v
    after phase 2 (if u != v):              best = max(best, mx[0][u], mx[0][v])
    return best

একটি লাফ মানে u থেকে up[k][u] পর্যন্ত ঠিক 2^k টি edge, আর mx[k][u] তাদের সর্বোচ্চ। LCA খোঁজার সময় u আর v যে লাফগুলো দেয়, সেগুলো মিলে ঠিক u → LCA আর v → LCA পথ দুটি ঢেকে ফেলে, কোনো edge দুবার না গুনে — তাই উত্তর সঠিক, সময় O(log n), বাড়তি জায়গা আরেকটি Θ(n log n) টেবিল। একই ছাঁচে min, gcd, যোগফল — যেকোনো associative operation. (যোগফলের জন্য অবশ্য rootDist-এর বিয়োগই সহজ।) কনটেস্টে এর ক্লাসিক ব্যবহার: minimum spanning tree (পর্ব ৪৫)-এ একটি নতুন edge যোগ করলে কোন edge বাদ যাবে — u থেকে v-এর পথের সবচেয়ে ভারী edge.

৭ · আরও দ্রুত — Euler tour + sparse table, আর offline পদ্ধতি

পর্ব ৩৭-এ (sparse table) একটি ঝলক দেখেছিলেন: LCA-কে একটি অ্যারের range minimum query-তে বদলে প্রতিটি প্রশ্ন O(1)-এ করা যায়। প্রধান উদাহরণে বিস্তারিত দেখি। root থেকে DFS চালান, আর প্রতিটি node-এ ঢোকার সময় এবং প্রতিটি সন্তান থেকে ফিরে আসার সময় সেই node-টি লিখুন। এই ক্রমের নাম Euler tour; n টি node-এ দৈর্ঘ্য 2n − 1 (প্রতিটি edge-এ একবার নামা আর একবার ওঠা, সাথে শুরুর root).

pos   :  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
node  :  1  2  4  7 10 12 10  7  4  8  4  2  5  2  1  3  6  9 11 13 11  9  6  3  1
depth :  0  1  2  3  4  5  4  3  2  3  2  1  2  1  0  1  2  3  4  5  4  3  2  1  0

first[12] = 5, first[8] = 9   ->  min depth on pos 5..9  is 2 at pos 8  ->  LCA(12, 8) = 4
first[12] = 5, first[13] = 19 ->  min depth on pos 5..19 is 0 at pos 14 ->  LCA(12, 13) = 1

first[v] হলো tour-এ v-এর প্রথম অবস্থান। কেন কাজ করে: ধরুন first[u] ≤ first[v] আর w = LCA(u, v). DFS u-তে ঢোকার পর v-তে পৌঁছানোর আগে w-এর subtree থেকে বের হয় না (v তো w-এর subtree-তেই), তাই এই অংশে w-এর চেয়ে কম গভীর কেউ নেই। আবার u আর v আলাদা শাখায় থাকলে u-এর শাখা থেকে v-এর শাখায় যেতে DFS-কে w-তে ফিরে আসতেই হয় — তাই w নিজে এই অংশে আছে। (u নিজে v-এর পূর্বপুরুষ হলে w = u, যে অংশের শুরুতেই আছে।) ফলে অংশটির সবচেয়ে কম depth-এর node-টিই w.

এখন tour-এর depth অ্যারের ওপর পর্ব ৩৭-এর sparse table বানান — min একটি idempotent operation, তাই দুটি ওভারল্যাপ করা ব্লকে প্রতিটি প্রশ্ন O(1). প্রস্তুতি: tour O(n), sparse table O(n log n) — অ্যারের দৈর্ঘ্য 2n − 1. টেবিলে depth-এর বদলে tour-এর index রাখুন, যাতে সর্বনিম্নের node-টি জানা যায়।

৮ · Subtree-র প্রশ্ন — entry/exit time আর একটানা রেঞ্জ

এবার অন্য ধরনের প্রশ্ন। একটি কোম্পানির ক্রমবিন্যাসে প্রতিটি কর্মীর একটি বেতন আছে, আর প্রশ্ন আসে: “এই ম্যানেজারের অধীনের সবার (তিনি নিজেসহ) মোট বেতন কত?”, মাঝে মাঝে “অমুকের বেতন বাড়ল”. অর্থাৎ subtree-র যোগফল, সাথে point update. প্রতিবার subtree ঘুরে যোগ করলে O(n). চতুর সমাধান: tree-কে এমন একটি সারিতে সাজান, যেখানে প্রতিটি subtree একটি একটানা অংশ.

DFS-এ প্রতিটি node-এ প্রথম ঢোকার সময় একটি ঘড়ির মান দিন — tin[v] = 0, 1, 2, … ক্রমে — আর v-এর পুরো subtree শেষ হলে tout[v] = এ পর্যন্ত দেওয়া সবচেয়ে বড় tin. এই দুটি সংখ্যাকে বলে entry/exit time (অনেকে এটিকেও Euler tour বলেন)। DFS v-তে ঢুকে তার subtree শেষ না করে বের হয় না, তাই v-এর subtree-র সবাই ঠিক tin[v] থেকে tout[v]-এর মধ্যে নম্বর পায় — আর অন্য কেউ সেখানে নয়।

এভাবে tree-র প্রশ্ন অ্যারের প্রশ্নে নেমে আসে, আর পুরো মডিউল ৫-এর হাতিয়ার কাজে লাগে: subtree-তে যোগ বা সর্বোচ্চ — segment tree (পর্ব ৩৪) বা Fenwick tree (পর্ব ৩৬); “পুরো subtree-র সবার বেতন ৫% বাড়াও” — lazy propagation (পর্ব ৩৫). আর একটি উপহার: u, v-এর পূর্বপুরুষ কি না, তা O(1)-এ — শর্ত tin[u] ≤ tin[v] এবং tout[v] ≤ tout[u]. অনেক binary lifting কোডে প্রথম phase-এর বদলে এই পরীক্ষা ব্যবহার করা হয়।

৯ · Tree-এর diameter — দুইবার BFS, আর কেন তা ঠিক

পর্ব ২৬-এ binary tree-তে diameter বের করেছিলেন একটি postorder দিয়ে — প্রতিটি node-এ “বাঁকের পথ” মেপে। যেকোনো সংখ্যক সন্তানের সাধারণ tree-তে, যেখানে ইনপুট শুধু edge-তালিকা, আরেকটি আশ্চর্য সরল পদ্ধতি আছে:

1. যেকোনো node s থেকে BFS চালিয়ে সবচেয়ে দূরের node a বের করুন।
2. a থেকে আবার BFS চালিয়ে সবচেয়ে দূরের node b বের করুন। a থেকে b-এর দূরত্বই diameter, আর a–b পথটিই একটি সবচেয়ে লম্বা পথ।

প্রমাণের রূপরেখা. মূল দাবি: যেকোনো s থেকে সবচেয়ে দূরের node a কোনো একটি সবচেয়ে লম্বা পথের প্রান্ত। ধরুন x–y একটি diameter, দৈর্ঘ্য D, আর d(·, ·) হলো tree-র দূরত্ব। দুই ক্ষেত্র:

• s থেকে a-এর পথ x–y পথকে ছোঁয়. s থেকে চলতে গিয়ে x–y পথে প্রথম যে node পড়ে, তার নাম c. তাহলে s থেকে x-এর আর y-এর পথও c দিয়ে যায়, তাই a সবচেয়ে দূরে বলে d(c, a) ≥ d(c, x) এবং d(c, a) ≥ d(c, y). c থেকে a-এর পথ x–y পথ ধরে বড়জোর একটি দিকে যেতে পারে; উল্টো দিকের প্রান্তটি নিন — ধরুন x. তাহলে x → c → a একটি সরল পথ, দৈর্ঘ্য d(x, c) + d(c, a) ≥ d(x, c) + d(c, y) = D. কোনো পথ D-এর চেয়ে লম্বা হতে পারে না — তাই x → c → a নিজেই একটি diameter, আর a তার প্রান্ত।
• দুই পথ একটিও node ভাগ করে না. tree connected, তাই দুই পথকে জোড়া দেওয়া একটি সংযোগ-পথ আছে: s–a পথের যে node p x–y পথের সবচেয়ে কাছে, তার থেকে x–y পথের সবচেয়ে কাছের node q পর্যন্ত, দৈর্ঘ্য ≥ 1. s থেকে x–y পথের যেকোনো node-এ যেতে হলে p আর q পেরোতেই হয়। ধরুন d(q, y) ≥ d(q, x), তাই d(q, y) ≥ D/2. a সবচেয়ে দূরে বলে d(s, a) ≥ d(s, y) = d(s, p) + d(p, q) + d(q, y), অর্থাৎ d(p, a) ≥ d(p, q) + d(q, y). তাহলে y → q → p → a পথের দৈর্ঘ্য d(y, q) + d(q, p) + d(p, a) ≥ 2·d(q, y) + 2·d(p, q) > D — অসম্ভব। তাই এই ক্ষেত্র ঘটেই না।

a একটি diameter-এর প্রান্ত হলে, a থেকে সবচেয়ে দূরের node b পর্যন্ত দূরত্ব অন্তত D (diameter-এর অন্য প্রান্ত তো আছেই), আর D-এর বেশি হতে পারে না — তাই d(a, b) = D. ∎ প্রমাণটি শুধু ধনাত্মক (বা শূন্য) edge-ওজনেই খাটে: ওজনসহ tree-তে BFS-এর বদলে DFS বা BFS দিয়ে rootDist-এর মতো ওজনের দূরত্ব মাপুন — tree-তে দুই node-এর পথ একটিই, তাই Dijkstra (পর্ব ৪৩) লাগে না। ঋণাত্মক ওজনে প্রমাণ ভাঙে; তখন পর্ব ২৬-এর মতো “বাঁকের পথ”-এর DP ব্যবহার করুন।

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
const int n = 13;
vector<vector<int>> adj(n + 1);
pair<int, vector<int>> bfs(int s) {                  // farthest node from s, and all distances
    vector<int> d(n + 1, -1); d[s] = 0; int far = s;
    queue<int> q; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (d[u] > d[far]) far = u;
        for (int v : adj[u]) if (d[v] < 0) { d[v] = d[u] + 1; q.push(v); }
    }
    return {far, d};
}
int main() {
    vector<pair<int, int>> edges{{1,2},{1,3},{2,4},{2,5},{3,6},{4,7},{4,8},{6,9},{7,10},{9,11},{10,12},{11,13}};
    for (auto [x, y] : edges) { adj[x].push_back(y); adj[y].push_back(x); }
    auto [a, d1] = bfs(5);                           // any start node works
    auto [b, d2] = bfs(a);
    cout << "BFS from 5: farthest = " << a << " at distance " << d1[a] << '\n';
    cout << "BFS from " << a << ": farthest = " << b << " at distance " << d2[b] << '\n';
    cout << "diameter path:";
    for (int x = b; ; ) {                            // walk back from b towards a
        cout << ' ' << x;
        if (x == a) break;
        for (int v : adj[x]) if (d2[v] == d2[x] - 1) { x = v; break; }
    }
    int brute = 0;                                   // O(n^2) check: BFS from every node
    for (int s = 1; s <= n; ++s) { auto [f, d] = bfs(s); brute = max(brute, d[f]); }
    cout << "\nbrute force diameter = " << brute << '\n';
}

BFS from 5: farthest = 13 at distance 7
BFS from 13: farthest = 12 at distance 10
diameter path: 12 10 7 4 2 1 3 6 9 11 13
brute force diameter = 10

from collections import deque

n = 13
edges = [(1,2),(1,3),(2,4),(2,5),(3,6),(4,7),(4,8),(6,9),(7,10),(9,11),(10,12),(11,13)]
adj = [[] for _ in range(n + 1)]
for a, b in edges:
    adj[a].append(b); adj[b].append(a)

def bfs(s):                                      # farthest node from s, and all distances
    d = [-1] * (n + 1); d[s] = 0; far = s
    q = deque([s])
    while q:
        u = q.popleft()
        if d[u] > d[far]: far = u
        for v in adj[u]:
            if d[v] < 0: d[v] = d[u] + 1; q.append(v)
    return far, d

a, d1 = bfs(5)                                   # any start node works
b, d2 = bfs(a)
print(f"BFS from 5: farthest = {a} at distance {d1[a]}")
print(f"BFS from {a}: farthest = {b} at distance {d2[b]}")
path = [b]                                       # walk back from b towards a
while path[-1] != a:
    x = path[-1]
    path.append(next(v for v in adj[x] if d2[v] == d2[x] - 1))
print("diameter path:", *path)
brute = max(max(bfs(s)[1]) for s in range(1, n + 1))   # O(n^2) check: BFS from every node
print(f"brute force diameter = {brute}")

BFS from 5: farthest = 13 at distance 7
BFS from 13: farthest = 12 at distance 10
diameter path: 12 10 7 4 2 1 3 6 9 11 13
brute force diameter = 10

Diameter-এর একটি উপহার — tree-র কেন্দ্র. একটি node-এর eccentricity হলো তার থেকে সবচেয়ে দূরের node-এর দূরত্ব; যার eccentricity সবচেয়ে কম, সে tree-র কেন্দ্র (center). প্রমাণ করা যায়, কেন্দ্র সব সময় diameter-এর ঠিক মাঝখানে — D জোড় হলে একটি node, বিজোড় হলে দুটি পাশাপাশি node — আর সর্বনিম্ন eccentricity ⌈D/2⌉. প্রধান উদাহরণে D = 10, তাই কেন্দ্র পথের ষষ্ঠ node, অর্থাৎ 1, আর তার eccentricity 5. একটি tree-নেটওয়ার্কে সার্ভার বসাতে চাইলে, যাতে সবচেয়ে দূরের যন্ত্রের দেরি সবচেয়ে কম হয় — কেন্দ্রই উত্তর।

আরও উন্নত কৌশলের এক ঝলক

১০ · AI-এর যুগে tree-এর কৌশল — দেখতে ঠিক, লুকানো ভুল

Binary lifting-এর কোড ২০ লাইনের, আর AI এটি প্রায় সব সময় পরিচিত চেহারায় লেখে। কিন্তু ভুল লুকিয়ে থাকে ঠিক সেই জায়গাগুলোয়, যেখানে ছোট পরীক্ষায় ধরা পড়ে না: LOG এক কম, root-এর parent 0 বা −1 রেখে অ্যারের বাইরে পড়া, দ্বিতীয় phase-এ !=-এর বদলে ==, বা টেবিলের লুপের ক্রম উল্টো। দুইবার BFS-এর ক্ষেত্রে AI প্রায়ই দাবি করে পদ্ধতিটি সাধারণ graph-এও চলে, বা ঋণাত্মক ওজনেও — দুটিই ভুল।

LCA আর diameter-এর কোড যাচাইয়ের চেকলিস্ট

• 2^LOG > n নিশ্চিত করেছি, আর root-এর parent root নিজে (বা আলাদা sentinel যার সব লাফ নিজের দিকে)
• টেবিল বানানোর বাইরের লুপ k-এর ওপর, যাতে up[k − 1] পুরো ভরা থাকে
• Edge case চালিয়েছি: u = v, একজন অন্যজনের পূর্বপুরুষ, root নিজে, এক node-এর tree, লম্বা শিকল
• ছোট এলোমেলো tree-তে দ্রুত LCA-কে সরল LCA-র সাথে, আর দুইবার BFS-কে সব-জোড়া brute force-এর সাথে মিলিয়েছি
• ওজনসহ দূরত্বে long long ব্যবহার করেছি — ২ লাখ edge × 10⁹ ওজন int-এ ধরে না
• Recursion ব্যবহার করলে গভীরতার সীমা ভেবেছি; নইলে BFS বা iterative DFS