Question
A file-system node is either a file with a non-negative byte size or a directory containing child nodes. Hard links are possible, so the same node object may be reachable by more than one path and cycles may exist. Implement: ```python def total_size(root) -> int: ... ``` Return the sum of the sizes of all distinct reachable files. Count a node at most once even if multiple paths reference it. An empty directory has size `0`. You may identify nodes by stable object identity. Aim for `O(V + E)` time and `O(V)` auxiliary space, where `V` is the number of distinct reachable nodes and `E` is the number of child references. ## Staged follow-ups 1. Provide an iterative traversal for inputs too deep for recursion. 2. Add memoization for repeated directory-size queries. 3. Support mutations and explain how cached totals are invalidated after adding, removing, or resizing a file. 4. Given an arbitrary entity ID, return its total size and define validity rules for the graph.