链接
题目
给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。
一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。
你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
如果你多次经过一条边，每一次经过都会给答案加一。
思路：看灵神的题解
将没有金币的叶节点全部干掉
因为最后收集完要回到起始点，所以相当于走过的路径又走了一遍
我们最后直接统计需要走的路径数，再*2就ok
代码如下
class Solution:
def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
n = len(coins)
# 构造图
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
# 得到每个点的度数
deg = list(map(len, g))
left_edges = n - 1
q = []
for i, (d, c) in enumerate(zip(deg, coins)):
# 找到没有金币的叶节点，
if d == 1 and c == 0:
q.append(i)
# 将其删除，直至删除完毕
while q:
left_edges -= 1
for y in g[q.pop()]:
deg[y] -= 1
if deg[y] == 1 and coins[y] == 0:
q.append(y)
# 找出所有有金币的叶子节点
for i, (d, c) in enumerate(zip(deg, coins)):
if d == 1 and c:
q.append(i)
left_edges -= len(q)
# 遍历所有有金币的叶子节点
for x in q:
for y in g[x]:
deg[y] -= 1
if deg[y] == 1:
left_edges -= 1
return max(left_edges * 2, 0)