# OA - Scale AI

###### Tags: `2023 Full-time OA`

## Platform Reward


from collections import defaultdict

class Solution:
    def dfs(self, node):
        if node in self.dp:
            return self.dp[node]
        
        node_descendants = 0
        node_reward = 0
        for neighbor in self.graph[node]:
            neighbor_reward, neighbor_descendants = self.dfs(neighbor)
            node_reward += (self.reward[neighbor] + neighbor_reward + neighbor_descendants)
            node_descendants += neighbor_descendants
        
        node_descendants += len(self.graph[node])

        self.dp[node] = [node_reward, node_descendants]    
        
        return self.dp[node]

    def solve(self, string):
        self.reward = defaultdict(int)
        self.graph = defaultdict(list)
        # node -> (sum_of_reward, num_descendants)
        self.dp = defaultdict(list)
        self.nodes = set()

        for segment in string.split(","):
            tar, src, reward = segment.split(" ")
            self.nodes.add(tar)
            self.reward[tar] = int(reward)
            if src != 'None':
                self.nodes.add(src)
                self.graph[src].append(tar)
            

        for node in self.nodes:
            self.dfs(node)
        
        rst = [node for node, _ in sorted(self.dp.items(), key = lambda x : (-x[1][0], x[0]))]

        return rst

S = Solution()
print(S.solve("A None 0,B C 5,C None 0,D A 10,E D -3"))