# 1916. Count Ways to Build Rooms in an Ant Colony

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def waysToBuildRooms(self, prevRoom: List[int]) -> int: kMod = 1_000_000_007 graph = collections.defaultdict(list) for i, prev in enumerate(prevRoom): graph[prev].append(i) def dfs(node: int) -> Tuple[int, int]: if not graph[node]: return 1, 1 ans = 1 l = 0 for child in graph[node]: temp, r = dfs(child) ans = (ans * temp * math.comb(l + r, r)) % kMod l += r return ans, l + 1 return dfs(0)[0]