LC 2603. 收集树中金币

https://leetcode.cn/problems/collect-coins-in-a-tree/

稍微有点难想到，看了题解之后才明白。

最开始我的想法非常直接，就是枚举每个节点，去判断”如果以这个节点为根，至少需要move到哪些节点才行“。但是这种算法的时间复杂度就是O(n^2).

我也考虑过是否可以做换根DP，我看讨论区里面也给出了这个解法，但是稍微有点难理解。

最后题解中给出的拓扑排序的算法算是看懂了。

首先将coin=0的叶子节点不断地递归删除掉，这样留下来的叶子节点都是有coin的（拓扑排序）
然后从这些叶子节点出发，判断至少需要到达那些节点(假设是X)，才能将这些叶子节点cover住
集合X中的节点肯定都是相连接并且没有回路的，走遍这些节点然后回来的长度就是 `2*(|X|-1)`

之前没有怎么写过无向图的拓扑排序，判断条件是 `ind[x]=1`. 然后在这种情况下面，可能ind[x]会变为负数，考虑0,1节点相连的情况。

然后在第二次遍历的时候，我们依然可以说使用 `ind[x]=1` 判断条件。

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        n = len(edges) + 1
        adj = [[] for _ in range(n)]
        ind = [0] * n
        for x, y in edges:
            adj[x].append(y)
            adj[y].append(x)
            ind[x] += 1
            ind[y] += 1

        # remove leaf node coin = 0
        from collections import deque
        q = deque()
        for i in range(n):
            if ind[i] == 1 and coins[i] == 0:
                q.append(i)
        while q:
            x = q.popleft()
            for y in adj[x]:
                ind[y] -= 1
                if ind[y] == 1 and coins[y] == 0:
                    q.append(y)

        # walk from leaf node to mark depth.
        q = deque()
        depth = [0] * n
        for i in range(n):
            if ind[i] == 1 and coins[i]:
                q.append(i)
                depth[i] = 0

        while q:
            x = q.popleft()
            for y in adj[x]:
                ind[y] -= 1
                # won't lead to coins = 0 leaf.
                if ind[y] == 1:
                    depth[y] = depth[x] + 1
                    q.append(y)

        edge = len([x for x in range(n) if depth[x] >= 2]) - 1
        if edge < 0: return 0
        ans = 2 * edge
        return ans