收集树中金币

难度: Hard

给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间有一条边。再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。

一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：

收集距离当前节点距离为 2 以内的所有金币，或者
移动到树中一个相邻节点。

你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。

如果你多次经过一条边，每一次经过都会给答案加一。

示例 1：

输入：coins = [1,0,0,0,0,1], edges = [[0,1],[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：从节点 2 出发，收集节点 0 处的金币，移动到节点 3 ，收集节点 5 处的金币，然后移动回节点 2 。

示例 2：

输入：coins = [0,0,0,1,1,0,0,1], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[5,6],[5,7]]
输出：2
解释：从节点 0 出发，收集节点 4 和 3 处的金币，移动到节点 2 处，收集节点 7 处的金币，移动回节点 0 。

提示：

n == coins.length
1 <= n <= 3 * 10⁴
0 <= coins[i] <= 1
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
edges 表示一棵合法的树。

Submission

运行时间: 197 ms

内存: 28.1 MB

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        # 拓扑排序去掉所有没有金币的叶子节点

        # 跑两轮拓扑排序，相当于去掉距离为2以内的点（选取这些点一定不是最优的）

        n=len(coins)
        e=[[]for _ in range(n)];ni=[0]*n

        for a,b in edges:
            e[a].append(b)
            e[b].append(a)
            ni[a]+=1
            ni[b]+=1
        
        has_bian=n-1

        #拓扑排序去无金币叶子节点
        q=deque()
        for i in range(n):
            if coins[i]==0 and ni[i]==1:    #既没有金币也是叶子节点的点去掉（加入队列）
                q.append(i)
                has_bian-=1
        
        while q:
            node=q.popleft()
            for j in e[node]:
                ni[j]-=1
                if coins[j]==0 and ni[j]==1:    #满足条件，加入队列
                    q.append(j)
                    has_bian-=1
        
        #跑两遍拓扑排序，剩余边数乘2就是答案（一来一回就2遍），q已经是空的了，可以再用
        # 可以等价于bfs再遍历该点的邻居
        for i in range(n):
            if ni[i]==1 and coins[i]==1:    #要去除的是有金币的叶子节点，不要重复统计已删掉的    
                q.append(i)
                has_bian-=1

        for ix in q:
            for jx in e[ix]:
                ni[jx]-=1
                if ni[jx]==1:           #这个点是第二轮的叶子，删掉
                    has_bian-=1
        
        return max(0,has_bian)*2          #最多可删除所有点，会得到负数，与0取一个max

Explain

题解的思路是通过拓扑排序来去除树中那些对解决问题没有直接帮助的节点，即那些没有金币且只有一个邻居（叶节点）的节点。首先，构建邻接表和每个节点的邻居数。然后，将所有没有金币的叶子节点加入队列，并通过拓扑排序逐个移除这些节点。经过一轮拓扑排序后，对剩下的树再进行一轮拓扑排序，特别处理有金币的叶子节点。最后，根据剩余的边数计算答案（来回各一次，所以乘以2），返回需要经过的最少边数。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def collectTheCoins(self, coins: List[int], edges: List[List[int]]) -> int:
        # 初始化邻接表和节点入度计数器
        n = len(coins)
        e = [[] for _ in range(n)]
        ni = [0] * n
        # 构建图的邻接表和更新节点的邻接数
        for a, b in edges:
            e[a].append(b)
            e[b].append(a)
            ni[a] += 1
            ni[b] += 1
        # 拓扑排序初始化
        q = deque()
        # 查找并移除没有金币的叶子节点
        for i in range(n):
            if coins[i] == 0 and ni[i] == 1:
                q.append(i)
        # 进行拓扑排序，移除这些节点
        while q:
            node = q.popleft()
            for j in e[node]:
                ni[j] -= 1
                if coins[j] == 0 and ni[j] == 1:
                    q.append(j)
        # 对有金币的叶子节点进行特别处理
        for i in range(n):
            if ni[i] == 1 and coins[i] == 1:
                q.append(i)
        # 再次拓扑排序处理
        while q:
            ix = q.popleft()
            for jx in e[ix]:
                ni[jx] -= 1
                if ni[jx] == 1:
                    q.append(jx)
        # 计算剩余边数的两倍作为结果
        has_bian = max(0, sum(ni)) # 计算剩余的边数
        return has_bian * 2

Explore

在题解中，被定义为'没有直接帮助的节点'的是那些没有金币且只有一个邻居（即叶节点）的节点。这些节点被认为对收集金币的最终目标没有贡献。因此，在拓扑排序的过程中，首先将这些节点识别并从图中移除，这样可以简化问题规模，同时减少不必要的遍历。

虽然拓扑排序通常用于有向图，但在这个问题中，它被用来逐层剥离无向树的外围叶节点。具体操作是，首先建立每个节点的邻接关系和邻居计数。然后，将所有无金币的叶节点（只有一个邻居的节点）加入队列，并逐一从队列中移除这些节点，同时更新其邻居的邻居计数。如果邻居节点因此变成了新的叶节点，且也没有金币，它们也会被加入队列进行后续移除。这种方法可以看作是树的层次剥离过程，逐步减少树的大小。

在拓扑排序后，对于那些依然保留有金币的叶节点，需要进行特别处理。这些节点是收集金币过程中的关键节点，因为它们是路径的必经之地。特别处理的逻辑是，将这些有金币的叶节点视为新的起点，再次执行拓扑排序，继续移除那些因为这个过程变成新的叶节点的节点。这是必要的，因为它确保了所有有金币的节点都被考虑在内，并且优化了必须经过的路径长度。

如果一个节点既有金币又只有一个邻居，这个节点不会在初次拓扑排序中被移除，因为它含有金币是必需的。在后续处理中，这类节点会被保留，并作为重要节点对待，因为它们是搜集路径的关键部分。即使它们是叶节点，也需要保留，因为它们对整体任务来说是价值节点。