Xét quốc gia biểu diễn bằng cây N nút, N-1 cạnh. Mỗi nút = trấn, cạnh = đường. 2 danh sách source, dest size N-1: đường i nối source[i] đến dest[i] (2 chiều). Danh sách population size N: population[i] = dân số trấn i. Nâng cấp một số trấn thành thành phố. Điều kiện: không 2 thành phố liền kề, và mọi nút liền kề trấn phải là thành phố (mọi đường nối trấn và thành phố). Tìm tổng dân số thành phố tối đa.
Ví dụ: source=[2,2,1,1], dest=[1,3,4,0], population=[6,8,4,3,5] → output 15 (nâng cấp 0,2,4: 6+4+5=15).
Quan sát: Đây là bài toán Maximum Weight Independent Set trên cây (tree DP). Mỗi nút hoặc là thành phố (chọn) hoặc trấn (không chọn). Ràng buộc: không 2 nút liền kề cùng chọn, và nút không chọn phải có tất cả neighbor được chọn → Đây là Vertex Cover tối thiểu trọng số ngược lại. Tương đương: chọn tập nút sao cho mọi cạnh có đúng 1 đầu được chọn (Perfect matching trên cây? Không, là Independent Set + Dominating Set = Kernel).
Giải pháp: DFS 2 trạng thái. dfs(x, choose) trả về max population từ subtree gốc x, với choose = True/False (x là thành phố/hay trấn). Nếu choose=True: cộng population[x], con bắt buộc choose=False. Nếu choose=False: con bắt buộc choose=True. Kết quả = max(dfs(0,True), sum(pop)-dfs(0,True)).
Triển khai
from collections import defaultdict
class Solution:
def solve(self, source, dest, population):
adj = defaultdict(list)
for a, b in zip(source, dest):
adj[a].append(b)
adj[b].append(a)
seen = set()
def dfs(x, choose):
if x in seen:
return 0
seen.add(x)
ans = 0
if choose:
ans += population[x]
for neighbor in adj[x]:
ans += dfs(neighbor, not choose)
return ans
x = dfs(0, True)
return max(x, sum(population) - x)
ob = Solution()
source = [2, 2, 1, 1]
dest = [1, 3, 4, 0]
population = [6, 8, 4, 3, 5]
print(ob.solve(source, dest, population))
Đầu vào
[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]
Đầu ra
15
Giải thích: Cây: 0-1-2, 2-3, 1-4. Chọn {0,2,4} (dân số 6+4+5=15) hoặc {1,3} (8+3=11). Max = 15. Code dùng seen tránh revisit (cây không chu trình).