পাইথনে ট্রি থেকে একটি এজ কাট করে দুটি সাবট্রিের নোড ভ্যালু সামের পার্থক্য মিনিমাইজ করা

n নোডবালা একটি ট্রি দেওয়া আছে (নোড ১ থেকে n)। প্রতিটি নোডের একটি ইন্টিজার ভ্যালু আছে। একটি এজ কাট করলে দুটি সাবট্রি বने। তাদের নোড ভ্যালু সামের পার্থক্য ন্যূনতম করতে হবে। এই ন্যূনতম পার্থক্য বের করতে হবে।

উদাহরণ

ইনপুট: n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]], values = [15,25,15,55,15,65]

আউটপুট: 0

এজ (1,3) কাট করলে দুটি সাবট্রির সাম ৯৫ এবং ৯৫ → পার্থক্য ০।

সমাধান পদ্ধতি

অ্যাডজেসেন্সি লিস্ট বানান।
লিফ নোডগুলো থেকে শুরুরে বটম-আপ DP করুন।
প্রতিটি নোডের সাবট্রি সাম ক্যালকুলেট করুন।
প্রতিটি নোড i (রুট বাদে) এর জন্য পার্থক্য = |total_sum - 2 * subtree_sum[i]|।
মিনিমাম পার্থক্য রিটার্ন করুন।

পাইথন ইমপ্লিমেন্টেশন

def solve(n, edge_list, values):
    adj_list = [[] for _ in range(n)]
    for u, v in edge_list:
        adj_list[u-1].append(v-1)
        adj_list[v-1].append(u-1)
    subtree_sum = [0] * n
    visited = [False] * n
    def dfs(u):
        visited[u] = True
        s = values[u]
        for v in adj_list[u]:
            if not visited[v]:
                s += dfs(v)
        subtree_sum[u] = s
        return s
    total = dfs(0)
    min_diff = float('inf')
    for i in range(1, n):
        diff = abs(total - 2 * subtree_sum[i])
        if diff < min_diff:
            min_diff = diff
    return min_diff

# টেস্ট
print(solve(6, [[1,2],[1,3],[2,4],[3,5],[3,6]], [10,20,10,50,10,60]))  # আউটপুট: 0

ইনপুট

6, [[1, 2], [1, 3], [2, 4], [3, 5], [3, 6]], [10, 20, 10, 50, 10, 60]