'''
keys: 
Solutions:
Similar: 
T:
S:
'''
from typing import List


"""
# Definition for Employee.
"""
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates


class Solution:
    # DFS, O(N) for S and T
    def getImportance(self, employees, query_id):
        emap = {e.id: e for e in employees}
        def dfs(eid):
            employee = emap[eid]
            return (employee.importance +
                    sum(dfs(eid) for eid in employee.subordinates))
        return dfs(query_id)
    
    
    # self-made, O(N) for S and T
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        if not employees or not id: return 0
        
        hashmap = {}
        for employee in employees:
            hashmap[employee.id] = (employee.importance, employee.subordinates)
        
        if id not in hashmap: return 0
        
        self.res = 0
        
        def vals_acc(id):
            val, subs = hashmap[id]
            self.res += val
            if not subs:
                return
            for sub in subs:
                vals_acc(sub)
        
        vals_acc(id)
        return self.res
            

