【LeetCode】收集树中金币

链接
题目

给你一个 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)