ডায়নামিক প্রোগ্রামিং৮ মিনিট পড়া

গাছে বা ট্রি-তে ডিপি (DP on Trees)

প্রতিটি নোডের উত্তর তার চাইল্ড বা সন্তানদের ওপর নির্ভর করে — নিচ থেকে ওপরে বা বটম-আপ পদ্ধতিতে হিসেব করুন

standard tree DP:\(O(n)\)tree knapsack:\(O(n^2)\)rerooting technique:\(O(n)\)

কল্পনা করুন একটি স্পোর্টস টিমের মোট স্কোর গণনা করছেন যেখানে প্রত্যেক খেলোয়াড়ের অবদান সরাসরি তাদের নিচের স্তরের খেলোয়াড়দের ওপর নির্ভর করে — কোচরা তাদের অ্যাসিস্ট্যান্টদের ওপর নির্ভরশীল, আর অ্যাসিস্ট্যান্টরা তাদের খেলোয়াড়দের ওপর। হেড কোচের স্কোর বের করতে হলে, আপনাকে প্রথমে প্রত্যেক খেলোয়াড়ের স্কোর জানতে হবে, তারপর প্রত্যেক অ্যাসিস্ট্যান্টের, এবং সবশেষে কোচের। এই নিচ থেকে ওপরের দিকে তথ্যের একত্রীকরণই হলো মূলত গাছে বা ট্রি-তে ডিপি (DP on Trees)।

ট্রি বা গাছের কোনো সাইকেল বা চক্র নেই, যার অর্থ হলো প্যারেন্ট-চাইল্ড (পিতা-সন্তান) দিকনির্দেশনা আপনাকে একটি স্বাভাবিক গণনার ক্রম প্রদান করে। প্যারেন্টের আগে সন্তানদের প্রসেস বা প্রক্রিয়া করুন — এটিই হলো ডিএফএস (DFS) পোস্ট-অর্ডার। আপনি যখন কোনো নোডে পৌঁছান, তখন তার সব চাইল্ডের বা সন্তানের ডিপি (DP) মান ইতিমধ্যেই প্রস্তুত থাকে।

বেসিক ট্রি ডিপি: পোস্ট-অর্ডার ডিএফএস (Post-Order DFS)

গাছটির যেকোনো নোডকে রুট (মূল) হিসেবে ধরুন। পোস্ট-অর্ডার ডিএফএসে, একটি নোড তখনই ভিজিট করা হয় যখন তার সাব-ট্রির সব বংশধরদের ভিজিট করা শেষ হয়। তাই যখন আপনি dp[node] হিসেব করবেন, তখন প্রত্যেক dp[child] ইতিমধ্যেই আপনার কাছে থাকবে। সাধারণত ডিপি স্টেট dp[node] মূলত "ওই নোডটি রুট হিসেবে থাকা সাব-ট্রির সেরা উত্তর" প্রকাশ করে।

উদাহরণ — সর্বাধিক পাথ সাম (Maximum Path Sum): dp[node] = এই নোড থেকে শুরু হওয়া নিচের দিকের কোনো পাথের সর্বোচ্চ যোগফল। dp[node] = node.val + max(0, max(dp[child] for all children))। পুরো উত্তরটি হয়তো কোনো নোডকে সর্বোচ্চ বিন্দু হিসেবে ব্যবহার করে অতিক্রম করতে পারে — সেক্ষেত্রে ব্যাস (diameter) বা সর্বোচ্চ পাথ খুঁজে পেতে এর দুটি সেরা চাইল্ড পাথ যোগ করুন।

ট্রি ন্যাপস্যাক (Tree Knapsack) — একটি সংযুক্ত সাব-ট্রি নির্বাচন করা

ট্রি থেকে সর্বোচ্চ k সংখ্যক নোড নির্বাচন করুন যাতে মোট ভ্যালু বা মান সর্বোচ্চ হয়, তবে শর্ত হলো: যদি কোনো নোড নির্বাচিত হয়, তবে তার প্যারেন্টকেও অবশ্যই নির্বাচিত হতে হবে (নির্বাচিত নোডগুলো একটি সংযুক্ত সাব-ট্রি গঠন করবে)। স্টেট: dp[node][j] = নোডের সাব-ট্রি থেকে ঠিক \(j\) সংখ্যক নোড ব্যবহার করে (যেখানে ওই নোড নিজেও অন্তর্ভুক্ত থাকবে) পাওয়া সর্বোচ্চ মান। একটি ন্যাপস্যাক-স্টাইল কম্বিনেশন ব্যবহার করে সন্তানদের এক এক করে মার্জ বা একত্রিত করুন। সতর্কভাবে ইমপ্লিমেন্ট করলে এর মোট সময় লাগে \(O(n^2)\)।

রিরুটিং (Rerooting) — যখন প্রতিটি নোডকেই রুট হওয়ার প্রয়োজন হয়

কখনো কখনো dp[node] এমন উত্তর প্রকাশ করে যেখানে নোডটি শুধু তার সাব-ট্রির নয়, বরং পুরো গাছের রুট হিসেবে কাজ করে। এটি সাধারণ নিয়মে হিসেব করা (প্রতিটি নোডকে রুট বা মূল ধরে আলাদা করে ডিএফএস চালানো) হবে \(O(n^2)\)।

রিরুটিং টেকনিক (rerooting technique) এটি মাত্র দুটি ডিএফএস পাসে সম্পন্ন করে:

ডাউন-পাস (DFS 1): নোড 0-কে রুট ধরে, down[v] হিসেব করুন = v-এর জন্য সাব-ট্রি উত্তর।

আপ-পাস (DFS 2): প্রতিটি নোড v-এর জন্য, up[v] হিসেব করুন = v-এর সাব-ট্রির বাইরের অংশ থেকে আসা সেরা উত্তর (v-এর প্যারেন্ট এবং প্যারেন্টের অন্যান্য সন্তানদের থেকে)। এখন down[v] এবং up[v] একত্রিত করে পুরো গাছের জন্য v-কে রুট ধরে উত্তরটি পেয়ে যান।

উদাহরণ — দূরত্বের সমষ্টি (Sum of Distances): প্রতিটি নোডের জন্য, অন্য সমস্ত নোডের মোট দূরত্ব কত তা খুঁজে বের করুন। দুটি ডিএফএস পাস এই কাজটি সকল n নোডের জন্য মোট \(O(n)\) সময়ে সম্পন্ন করে।

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

ট্রি ডিপি — একটি গাছের ব্যাস (Diameter of a Tree)

from collections import defaultdict

def tree_diameter(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    diameter = [0]

    def dfs(node, parent):
        # Returns the longest downward path starting from a node
        best1 = best2 = 0  # two longest child paths
        for child in graph[node]:
            if child == parent:
                continue
            d = dfs(child, node) + 1
            if d >= best1: best1, best2 = d, best1
            elif d > best2: best2 = d
        diameter[0] = max(diameter[0], best1 + best2)
        return best1

    dfs(0, -1)
    return diameter[0]

print(tree_diameter(5, [(0,1),(1,2),(2,3),(1,4)]))  # 3
print(tree_diameter(4, [(0,1),(1,2),(1,3)]))         # 2