হেভি-লাইট ডিকম্পোজিশন#

হেভি-লাইট ডিকম্পোজিশন হলো একটি মোটামুটি সাধারণ টেকনিক যা আমাদের কার্যকরভাবে এমন অনেক সমস্যা সমাধান করতে দেয় যেগুলো ট্রি-তে কুয়েরি তে পরিণত হয়।

বর্ণনা#

ধরা যাক, একটি ইচ্ছামতো রুট বিশিষ্ট $n$ টি ভার্টেক্সের একটি ট্রি $G$ আছে।

এই ট্রি ডিকম্পোজিশনের সারমর্ম হলো ট্রি-কে কয়েকটি পাথে বিভক্ত করা যাতে যেকোনো $v$ থেকে রুট ভার্টেক্সে পৌঁছাতে সর্বাধিক $\log n$ টি পাথ অতিক্রম করতে হয়। এছাড়া, এই পাথগুলোর কোনোটি অন্যটির সাথে ছেদ করা উচিত নয়।

এটি স্পষ্ট যে যদি আমরা যেকোনো ট্রি-র জন্য এমন একটি ডিকম্পোজিশন খুঁজে পাই, তাহলে এটি আমাদের "$a$ থেকে $b$ পাথে কিছু গণনা করো" ধরনের নির্দিষ্ট একক কুয়েরিগুলোকে "$k$-তম পাথের $[l, r]$ সেগমেন্টে কিছু গণনা করো" ধরনের একাধিক কুয়েরিতে রূপান্তর করতে দেবে।

নির্মাণ অ্যালগরিদম#

আমরা প্রতিটি ভার্টেক্স $v$ এর জন্য তার সাবট্রি-র আকার $s(v)$ গণনা করি, অর্থাৎ ভার্টেক্স $v$ এর সাবট্রি-তে ভার্টেক্সের সংখ্যা যেটিতে $v$ নিজেও অন্তর্ভুক্ত।

এরপর, একটি ভার্টেক্স $v$ এর চাইল্ডদের দিকে যাওয়া সমস্ত এজ বিবেচনা করি। আমরা একটি এজকে হেভি বলি যদি এটি এমন একটি ভার্টেক্স $c$ তে নিয়ে যায় যাতে:

$$ s(c) \ge \frac{s(v)}{2} \iff \text{edge }(v, c)\text{ is heavy} $$

অন্যান্য সব এজকে লাইট হিসেবে লেবেল করা হয়।

এটি স্পষ্ট যে একটি ভার্টেক্স থেকে নিচের দিকে সর্বাধিক একটি হেভি এজ বের হতে পারে, কারণ অন্যথায় ভার্টেক্স $v$ এর কমপক্ষে $\ge \frac{s(v)}{2}$ আকারের দুটি চাইল্ড থাকত, এবং তাই $v$ এর সাবট্রি-র আকার অনেক বড় হয়ে যেত, $s(v) \ge 1 + 2 \frac{s(v)}{2} > s(v)$, যা একটি বৈপরীত্য।

এখন আমরা ট্রি-কে ডিসজয়েন্ট পাথে বিভক্ত করব। সেই সমস্ত ভার্টেক্স বিবেচনা করি যেখান থেকে নিচের দিকে কোনো হেভি এজ আসে না। আমরা প্রতিটি এমন ভার্টেক্স থেকে উপরে যাব যতক্ষণ না ট্রি-র রুটে পৌঁছাই বা একটি লাইট এজের মধ্য দিয়ে যাই। ফলে, আমরা কয়েকটি পাথ পাব যেগুলো শূন্য বা তার বেশি হেভি এজ এবং একটি লাইট এজ দিয়ে গঠিত। রুটে শেষ হওয়া পাথটি এর ব্যতিক্রম এবং এতে লাইট এজ থাকবে না। এগুলোকে হেভি পাথ বলি - এগুলোই হেভি-লাইট ডিকম্পোজিশনের কাঙ্ক্ষিত পাথ।

সঠিকতার প্রমাণ#

প্রথমত, আমরা লক্ষ্য করি যে অ্যালগরিদম দ্বারা প্রাপ্ত হেভি পাথগুলো ডিসজয়েন্ট হবে। আসলে, যদি দুটি এমন পাথের একটি কমন এজ থাকত, তাহলে এর মানে হতো একটি ভার্টেক্স থেকে দুটি হেভি এজ বের হচ্ছে, যা অসম্ভব।

দ্বিতীয়ত, আমরা দেখাব যে ট্রি-র রুট থেকে যেকোনো ইচ্ছামতো ভার্টেক্সে নামতে গিয়ে, আমরা পথে সর্বাধিক $\log n$ টি হেভি পাথ পরিবর্তন করব। একটি লাইট এজ বরাবর নামলে বর্তমান সাবট্রি-র আকার অর্ধেক বা তার কমে নেমে আসে:

$$ s(c) < \frac{s(v)}{2} \iff \text{edge }(v, c)\text{ is light} $$

তাই, সাবট্রি আকার এক হওয়ার আগে আমরা সর্বাধিক $\log n$ টি লাইট এজের মধ্য দিয়ে যেতে পারি।

যেহেতু আমরা একটি হেভি পাথ থেকে অন্যটিতে শুধুমাত্র একটি লাইট এজের মধ্য দিয়ে যেতে পারি (প্রতিটি হেভি পাথের, রুটে শুরু হওয়াটি ব্যতীত, একটি লাইট এজ থাকে), আমরা রুট থেকে যেকোনো ভার্টেক্সে যাওয়ার পাথে সর্বাধিক $\log n$ বারের বেশি হেভি পাথ পরিবর্তন করতে পারি না, যা প্রয়োজন ছিল।

নিম্নলিখিত চিত্রটি একটি নমুনা ট্রি-র ডিকম্পোজিশন দেখায়। হেভি এজগুলো লাইট এজের চেয়ে মোটা। হেভি পাথগুলো ডটেড সীমারেখা দ্বারা চিহ্নিত।

নমুনা সমস্যা#

সমস্যা সমাধানের সময়, হেভি-লাইট ডিকম্পোজিশনকে কখনো কখনো ভার্টেক্স ডিসজয়েন্ট পাথের সেট হিসেবে (এজ ডিসজয়েন্ট পাথের পরিবর্তে) বিবেচনা করা বেশি সুবিধাজনক। এটি করতে, প্রতিটি হেভি পাথের শেষ এজটি যদি লাইট এজ হয় তাহলে সেটি বাদ দেওয়াই যথেষ্ট, তাহলে কোনো বৈশিষ্ট্য লঙ্ঘিত হয় না, কিন্তু এখন প্রতিটি ভার্টেক্স ঠিক একটি হেভি পাথে থাকে।

নিচে আমরা কিছু সাধারণ কাজ দেখব যেগুলো হেভি-লাইট ডিকম্পোজিশনের সাহায্যে সমাধান করা যায়।

আলাদাভাবে, পাথে সংখ্যার যোগফল সমস্যাটিতে মনোযোগ দেওয়া উচিত, কারণ এটি এমন একটি সমস্যার উদাহরণ যেটি সরলতর টেকনিক দিয়ে সমাধান করা যায়।

দুটি ভার্টেক্সের মধ্যে পাথে সর্বাধিক মান#

একটি ট্রি দেওয়া আছে, প্রতিটি ভার্টেক্সে একটি মান নির্ধারিত। $(a, b)$ আকারের কুয়েরি আছে, যেখানে $a$ এবং $b$ ট্রি-র দুটি ভার্টেক্স, এবং ভার্টেক্স $a$ এবং $b$ এর মধ্যে পাথে সর্বাধিক মান বের করতে হবে।

আমরা আগে থেকে ট্রি-র হেভি-লাইট ডিকম্পোজিশন তৈরি করি। প্রতিটি হেভি পাথের উপর আমরা একটি সেগমেন্ট ট্রি তৈরি করব, যেটি নির্দিষ্ট হেভি পাথের নির্দিষ্ট সেগমেন্টে সর্বাধিক নির্ধারিত মান বিশিষ্ট ভার্টেক্স $\mathcal{O}(\log n)$ এ খুঁজতে দেবে। যদিও হেভি-লাইট ডিকম্পোজিশনে হেভি পাথের সংখ্যা $n - 1$ পর্যন্ত হতে পারে, সমস্ত পাথের মোট আকার $\mathcal{O}(n)$ দ্বারা সীমাবদ্ধ, তাই সেগমেন্ট ট্রি-গুলোর মোট আকারও লিনিয়ার হবে।

$(a, b)$ কুয়েরির উত্তর দিতে, আমরা $a$ এবং $b$ এর লোয়েস্ট কমন অ্যানসেস্টর $l$ বের করি, যেকোনো পছন্দের পদ্ধতিতে। এখন কাজটি দুটি কুয়েরি $(a, l)$ এবং $(b, l)$ এ পরিণত হয়, যাদের প্রতিটির জন্য আমরা নিম্নলিখিত করতে পারি: নিচের ভার্টেক্সটি কোন হেভি পাথে আছে তা খুঁজে বের করি, এই পাথে একটি কুয়েরি করি, এই পাথের শীর্ষে যাই, আবার নির্ধারণ করি আমরা কোন হেভি পাথে আছি এবং সেখানে একটি কুয়েরি করি, এভাবে চলতে থাকি, যতক্ষণ না $l$ ধারণকারী পাথে পৌঁছাই।

একটি ক্ষেত্রে সতর্ক থাকা উচিত যখন, উদাহরণস্বরূপ, $a$ এবং $l$ একই হেভি পাথে থাকে - তখন এই পাথে ম্যাক্সিমাম কুয়েরি যেকোনো প্রিফিক্সে নয়, বরং $a$ এবং $l$ এর মধ্যবর্তী অভ্যন্তরীণ অংশে করতে হবে।

$(a, l)$ এবং $(b, l)$ সাব-কুয়েরির প্রতিটিতে উত্তর দিতে $\mathcal{O}(\log n)$ টি হেভি পাথের মধ্য দিয়ে যেতে হয় এবং প্রতিটি পাথে একটি ম্যাক্সিমাম কুয়েরি করা হয় পাথের কিছু অংশে, যার জন্য আবার সেগমেন্ট ট্রি-তে $\mathcal{O}(\log n)$ অপারেশন প্রয়োজন। অতএব, একটি $(a, b)$ কুয়েরি $\mathcal{O}(\log^2 n)$ সময় নেয়।

আপনি যদি অতিরিক্তভাবে প্রতিটি হেভি পাথের সমস্ত প্রিফিক্সের ম্যাক্সিমাম গণনা ও সংরক্ষণ করেন, তাহলে আপনি একটি $\mathcal{O}(\log n)$ সমাধান পান কারণ সমস্ত ম্যাক্সিমাম কুয়েরি প্রিফিক্সে হয় পূর্বসূরি $l$ এ পৌঁছানোর সময় সর্বাধিক একবার ব্যতীত।

দুটি ভার্টেক্সের মধ্যে পাথে সংখ্যার যোগফল#

একটি ট্রি দেওয়া আছে, প্রতিটি ভার্টেক্সে একটি মান নির্ধারিত। $(a, b)$ আকারের কুয়েরি আছে, যেখানে $a$ এবং $b$ ট্রি-র দুটি ভার্টেক্স, এবং ভার্টেক্স $a$ এবং $b$ এর মধ্যে পাথের মানগুলোর যোগফল বের করতে হবে। এই কাজের একটি ভ্যারিয়েন্ট সম্ভব যেখানে অতিরিক্তভাবে আপডেট অপারেশন আছে যেগুলো এক বা একাধিক ভার্টেক্সে নির্ধারিত সংখ্যা পরিবর্তন করে।

এই কাজটি পূর্ববর্তী ম্যাক্সিমাম সমস্যার মতোই হেভি-লাইট ডিকম্পোজিশন দিয়ে সমাধান করা যায় হেভি পাথের উপর সেগমেন্ট ট্রি তৈরি করে। আপডেট না থাকলে প্রিফিক্স সাম ব্যবহার করা যায়। তবে, এই সমস্যাটি সরলতর টেকনিক দিয়েও সমাধান করা যায়।

আপডেট না থাকলে, দুটি ভার্টেক্সের মধ্যে পাথে যোগফল বাইনারি লিফটিং দ্বারা দুটি ভার্টেক্সের LCA খোঁজার সাথে সাথেই বের করা সম্ভব — এর জন্য, প্রতিটি ভার্টেক্সের $2^k$-তম পূর্বসূরির সাথে সাথে প্রিপ্রসেসিং-এর সময় সেই পূর্বসূরিদের পর্যন্ত পাথের যোগফলও সংরক্ষণ করা প্রয়োজন।

এই সমস্যার জন্য একটি মৌলিকভাবে ভিন্ন পদ্ধতি আছে - ট্রি-র অয়লার ট্যুর বিবেচনা করা, এবং এর উপর একটি সেগমেন্ট ট্রি তৈরি করা। এই অ্যালগরিদমটি একটি সমজাতীয় সমস্যার নিবন্ধে আলোচিত। আবারও, আপডেট না থাকলে প্রিফিক্স সাম সংরক্ষণই যথেষ্ট এবং সেগমেন্ট ট্রি-র প্রয়োজন নেই।

এই উভয় পদ্ধতিই তুলনামূলক সরল সমাধান দেয় যেটি একটি কুয়েরির জন্য $\mathcal{O}(\log n)$ সময় নেয়।

দুটি ভার্টেক্সের মধ্যে পাথের এজ পুনরায় রং করা#

একটি ট্রি দেওয়া আছে, প্রতিটি এজ প্রাথমিকভাবে সাদা রং করা। $(a, b, c)$ আকারের আপডেট আছে, যেখানে $a$ এবং $b$ দুটি ভার্টেক্স এবং $c$ একটি রং, যা নির্দেশ করে যে $a$ থেকে $b$ পাথের সমস্ত এজ $c$ রংয়ে পুনরায় রং করতে হবে। সমস্ত পুনঃরং করার পর, প্রতিটি রংয়ের কতটি এজ পাওয়া গেছে তা জানাতে হবে।

উপরের সমস্যাগুলোর মতোই, সমাধান হলো কেবল হেভি-লাইট ডিকম্পোজিশন প্রয়োগ করা এবং প্রতিটি হেভি পাথের উপর একটি সেগমেন্ট ট্রি তৈরি করা।

$(a, b)$ পাথে প্রতিটি পুনঃরং দুটি আপডেট $(a, l)$ এবং $(b, l)$ এ পরিণত হবে, যেখানে $l$ হলো ভার্টেক্স $a$ এবং $b$ এর লোয়েস্ট কমন অ্যানসেস্টর। $\mathcal{O}(\log n)$ পাথের জন্য প্রতি পাথ $\mathcal{O}(\log n)$ করে, ফলে প্রতি আপডেটে $\mathcal{O}(\log^2 n)$ কমপ্লেক্সিটি।

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

উপরে আলোচিত পদ্ধতির কিছু অংশ দক্ষতা না হারিয়ে ইমপ্লিমেন্টেশন সহজ করতে পরিবর্তন করা যেতে পারে।

হেভি এজ এর সংজ্ঞা পরিবর্তন করে সবচেয়ে বড় সাবট্রি বিশিষ্ট চাইল্ডে যাওয়া এজ করা যায়, সমান হলে ইচ্ছামতো ভাঙা যায়। এতে কিছু লাইট এজ হেভিতে রূপান্তরিত হতে পারে, যার মানে কিছু হেভি পাথ মিলিত হয়ে একটি একক পাথ গঠন করবে, কিন্তু সব হেভি পাথ ডিসজয়েন্ট থাকবে। এটিও নিশ্চিত যে একটি লাইট এজ বরাবর নামলে সাবট্রি আকার অর্ধেক বা তার কমে নামে।
প্রতিটি হেভি পাথের উপর আলাদা সেগমেন্ট ট্রি তৈরির পরিবর্তে, একটি একক সেগমেন্ট ট্রি ব্যবহার করা যায় যেখানে প্রতিটি হেভি পাথে ডিসজয়েন্ট সেগমেন্ট বরাদ্দ করা হয়।
কুয়েরির উত্তর দিতে LCA গণনার প্রয়োজনের কথা উল্লেখ করা হয়েছে। LCA আলাদাভাবে গণনা করা যায়, তবে কুয়েরির উত্তর দেওয়ার প্রক্রিয়ায় LCA গণনা সংহত করাও সম্ভব।

হেভি-লাইট ডিকম্পোজিশন সম্পাদন করতে:

vector<int> parent, depth, heavy, head, pos;
int cur_pos;

int dfs(int v, vector<vector<int>> const& adj) {
    int size = 1;
    int max_c_size = 0;
    for (int c : adj[v]) {
        if (c != parent[v]) {
            parent[c] = v, depth[c] = depth[v] + 1;
            int c_size = dfs(c, adj);
            size += c_size;
            if (c_size > max_c_size)
                max_c_size = c_size, heavy[v] = c;
        }
    }
    return size;
}

void decompose(int v, int h, vector<vector<int>> const& adj) {
    head[v] = h, pos[v] = cur_pos++;
    if (heavy[v] != -1)
        decompose(heavy[v], h, adj);
    for (int c : adj[v]) {
        if (c != parent[v] && c != heavy[v])
            decompose(c, c, adj);
    }
}

void init(vector<vector<int>> const& adj) {
    int n = adj.size();
    parent = vector<int>(n);
    depth = vector<int>(n);
    heavy = vector<int>(n, -1);
    head = vector<int>(n);
    pos = vector<int>(n);
    cur_pos = 0;

    dfs(0, adj);
    decompose(0, 0, adj);
}

ট্রি-র অ্যাডজেসেন্সি লিস্ট init ফাংশনে পাস করতে হবে, এবং ডিকম্পোজিশন ভার্টেক্স 0 কে রুট ধরে সম্পাদিত হয়।

dfs ফাংশনটি প্রতিটি ভার্টেক্স v এর জন্য heavy[v] গণনা করতে ব্যবহৃত হয়, যেটি হলো $v$ থেকে হেভি এজের অপর প্রান্তের চাইল্ড। এছাড়া dfs প্রতিটি ভার্টেক্সের প্যারেন্ট এবং ডেপথও সংরক্ষণ করে, যা পরে কুয়েরির সময় কাজে লাগবে।

decompose ফাংশনটি প্রতিটি ভার্টেক্স v এর জন্য head[v] এবং pos[v] মান নির্ধারণ করে, যেগুলো যথাক্রমে v যে হেভি পাথে আছে তার হেড এবং সমস্ত ভার্টেক্স কভার করা একক সেগমেন্ট ট্রি-তে v এর অবস্থান।

পাথে কুয়েরির উত্তর দিতে, উদাহরণস্বরূপ আলোচিত ম্যাক্সিমাম কুয়েরি, আমরা এরকম কিছু করতে পারি:

int query(int a, int b) {
    int res = 0;
    for (; head[a] != head[b]; b = parent[head[b]]) {
        if (depth[head[a]] > depth[head[b]])
            swap(a, b);
        int cur_heavy_path_max = segment_tree_query(pos[head[b]], pos[b]);
        res = max(res, cur_heavy_path_max);
    }
    if (depth[a] > depth[b])
        swap(a, b);
    int last_heavy_path_max = segment_tree_query(pos[a], pos[b]);
    res = max(res, last_heavy_path_max);
    return res;
}