ปัญหา: Country = Tree (N Nodes, N-1 Edges) Node = Town, Edge = Road Bidirectional
Population[i] = ประชากร Town i
Upgrade Towns → Cities ภายใต้เงื่อนไข:
- No two Cities adjacent (Independent Set)
- Every Town ต้องติด City (Vertex Cover)
เงื่อนไข 1+2 → Cities = Max Independent Set ที่เป็น Vertex Cover ด้วย = Maximum Weight Independent Set บน Tree
Key Insight: Tree = Bipartite Graph
Tree เป็น Bipartite เสมอ สามารถ 2-Color ได้ (Black/White)
เงื่อนไข "No Adjacent Cities" + "Every Town adjacent to City" → Cities ต้องเป็นหนึ่งในสอง Color Class ทั้งหมด
→ คำตอบ = max(Sum of Black Nodes, Sum of White Nodes)
อัลกอริทึม: DFS 2-Coloring
from collections import defaultdict
class Solution:
def solve(self, source, dest, population):
# Build Adjacency List
adj = defaultdict(list)
for a, b in zip(source, dest):
adj[a].append(b)
adj[b].append(a)
seen = set()
def dfs(node, choose):
"""Return population sum if we choose/skip this node's color"""
if node in seen:
return 0
seen.add(node)
total = population[node] if choose else 0
for nei in adj[node]:
total += dfs(nei, not choose) # Alternate color
return total
# Start from Node 0, Choose = True (Color 0)
color0_sum = dfs(0, True)
total_pop = sum(population)
color1_sum = total_pop - color0_sum
return max(color0_sum, color1_sum)
# Test
ob = Solution()
source = [2, 2, 1, 1]
dest = [1, 3, 4, 0]
population = [6, 8, 4, 3, 5]
print(ob.solve(source, dest, population)) # 15
คำอธิบาย
สร้าง Adjacency List จาก Source/Dest
DFS 2-Coloring: สลับ `choose` ทุก Level (True/False = 2 สี)
`color0_sum` = Pop ของ Color 0 (เริ่ม Node 0 = True)
`color1_sum` = Total - Color0 = Pop ของ Color 1
คำตอบ = max(Color0, Color1)
ตัวอย่างการทำงาน
Edges: 2-1, 2-3, 1-4, 1-0
Tree:
2
/ \
1 3
/ \
4 0
2-Coloring (Start 2=Color0):
Color 0: Nodes {2, 4, 0} → Pop = 4 + 3 + 6 = 13
Color 1: Nodes {1, 3} → Pop = 8 + 5 = 13
Wait... โค้ดเริ่มจาก Node 0:
Color 0: {0, 1, 3} → 6 + 8 + 5 = 19?
Let's trace:
dfs(0, True): choose 0 (6) + dfs(1, False)
dfs(1, False): skip 1 (0) + dfs(2, True) + dfs(4, True)
dfs(2, True): choose 2 (4) + dfs(3, False)
dfs(3, False): skip 3 (0)
dfs(4, True): choose 4 (5)
Total Color0 = 6 + 0 + 4 + 0 + 5 = 15
Color1 = 26 - 15 = 11
Max = 15 ✓
Complexity
- Time: O(N) - Visit แต่ละ Node/Edge 1 ครั้ง
- Space: O(N) - Adjacency List + Recursion Stack
Generalization: Maximum Weight Independent Set on Tree (DP)
หากเงื่อนไขเปลี่ยน (ไม่บังคับ Vertex Cover) ใช้ Tree DP:
def dfs(u, parent):
take = population[u]
skip = 0
for v in adj[u]:
if v != parent:
child_take, child_skip = dfs(v, u)
take += child_skip # ถ้า Take u → Child ต้อง Skip
skip += max(child_take, child_skip) # ถ้า Skip u → Child อะไรก็ได้
return take, skip
ans = max(dfs(0, -1))
