1
class Solution {
2
 public:
3
  int ans = INT_MIN, tmp = 0;
4
  unordered_map<int, vector<int>> mp; // manager to each subordination
5
  vector<int> *pInformTime;
6
  int numOfMinutes(int n, int headID, vector<int> &manager, vector<int> &informTime) {
7
    pInformTime = &informTime;
8
    for (int i = 0; i < n; i++) mp[manager[i]].push_back(i);
9
    dfs(headID);
10
    return ans;
11
  }
12
  void dfs(int i) {
13
    if (mp.find(i) == mp.end()) {
14
      ans = max(ans, tmp);
15
    } else {
16
      tmp += (*pInformTime)[i];
17
      for (auto &c : mp[i]) dfs(c);
18
      tmp -= (*pInformTime)[i];
19
    }
20
  }
21
};