题解 | #牛牛掷硬币#

根据题意,我们可以建立一个有向无环图,并统计其入度,之后在图上进行拓扑排序,每次当我们遍历到一个节点时,判断其是否可以解决自身产生的问题,同时我们记录每个成员当前所接受的其他问题,分别统计解决问题个数即可。

import collections
class Solution:
    def solve(self , n , a , p , k ):
        # write code here
        ans = [0] * n
        edges = collections.defaultdict(int)
        indegree = [0] * n
        for i in range(n - 1):
            edges[i + 1] = p[i] - 1
            indegree[p[i] - 1] += 1

        queue = []
        que = collections.defaultdict(list)
        visited = set()
        for i in range(len(indegree)):
            if indegree[i] == 0:
                queue.append(i)
                visited.add(i)

        while queue:
            cur_node = queue.pop(0)
            if cur_node == 0:
                g = -1
            else:
                g = edges[cur_node]

            if k[cur_node] <= a[cur_node]:
                ans[cur_node] += 1
            else:
                if g != -1:
                    que[g].append(k[cur_node])
            for q in que[cur_node]:
                if q <= a[cur_node]:
                    ans[cur_node] += 1
                else:
                    if g != -1:
                        que[g].append(q)
            if g != -1:
                indegree[g] -= 1
                if indegree[edges[cur_node]] == 0 and edges[cur_node] not in visited:
                    visited.add(edges[cur_node])
                    queue.append(edges[cur_node])
        return ans