โปรแกรมหาความต่างน้อยที่สุดของผลรวมโหนดในสอง subtree ใน Python

มีต้นไม้ n โหนด แต่ละโหนดมีค่า ตัดขอบหนึ่งขอบ ให้ความต่างของผลรวมค่าโหนดในสอง subtree น้อยที่สุด

ตัวอย่าง: n=6, edges=[[1,2],[1,3],[2,4],[3,5],[3,6]], values=[10,20,10,50,10,60] → 0

ขั้นตอนการแก้ปัญหา

1. สร้าง adjacency list
2. คำนวณผลรวม subtree ทุกโหนดด้วย DFS (post-order)
3. สำหรับแต่ละขอบ (u,v) โดย v เป็นลูกของ u: ความต่าง = |total_sum - 2 * subtree_sum[v]|
4. หาค่าต่ำสุด

ตัวอย่างโค้ด Python

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

# ทดสอบ
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]

เอาต์พุตตัวอย่าง

0