程序以python查找所有城市的最大可能人口
考虑一个表示为具有N个节点和N-1边缘的树的国家。现在，每个节点代表一个城镇，每个边沿代表一条道路。我们有两个数字列表，分别是大小为N-1的数字源和目标。根据他们，第i条道路将source[i]连接到dest[i]。道路是双向的。我们还有另一个数字列表，称为人口规模N，其中，人口[i]代表第i个镇的人口。我们正在尝试将一些城镇升级为城市。但是，不应有两个城市彼此相邻，并且与城镇相邻的每个节点都应该是一个城市（每条道路都必须连接一个城镇和一个城市）。因此，我们必须找到所有城市的最大可能人口。
因此，如果输入类似于source=[2，2，1，1]dest=[1，3，4，0]人口=[6，8，4，4，3，5]，那么输出将为15，因为我们可以将城市0、2和4升级为6+4+5=15的人口。
为了解决这个问题，我们将遵循以下步骤-
adj：=通过使用source和dest创建图的邻接表
定义一个功能dfs()。这将需要x，选择
如果看到x，则
返回0
将x标记为可见
回答：=0
如果选择为真，则
ans：=ans+人口[x]
对于adj[x]中的每个邻居，执行
ans：=ans+dfs（邻居，选择逆）
返回ans
从主要方法执行以下操作：
x：=dfs（0，真）
返回x和（（总和）-x）的最大值
让我们看下面的实现以更好地理解-
例
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))输入值
[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]
输出结果
15