P3509. 文件目录大小

解题思路

注意，本题的思路以及解法和 【BFS】2025A-BOSS的收入 非常类似。

DFS 解法

当我们查询编号为 target_idx 的文件目录时，我们必须统计其下面所有子文件夹的目录总和。换句话说，某一个节点的总大小，是由其下面所有的节点的和来决定的。

我们需要一个长度为 M 的哈希表 size_table，用来存放每一个目录的大小。

我们构建邻接表，键为父节点的 id，值为其子节点 id 所构成的列表。

由于 DFS 需要用递归来解决，我们考虑 递归三要素：

• 递归的子问题：对于某一个父节点，将每一个子节点的大小加入到父节点的大小中。
• 递归终止条件：当前文件目录 cur_idx 不存在任何一个子目录，无需再进行向下递归。
• 递归入口编写：将 target_idx 作为实参传入 dfs() 函数的参数 cur_idx 中，表示从查询节点 target_idx 开始进行搜索。

因此可以构造这样的 DFS 函数以及调用：

BFS 拓扑排序解法

显然这个树形结构也存在依赖关系：如果要计算某个父节点的大小，必须将其所有的子节点都计算完毕后才行。在这个角度上，父节点大小的计算实际上是依赖于其所有子节点的。

如果画成有向图的话，在计算大小的问题上，边的方向是从子节点指向父节点。因此在数据储存上，我们需要反过来构建邻接表，以子节点为键，子节点对应的父节点为值。当然，在 DFS 解法中存放每一个目录的大小的哈希表 size_table 也是需要的。在处理原始数据的过程中，我们也可以同时构建入度表 indegree_list。

因此我们可以将所有叶节点（不包含子节点的节点）作为拓扑排序的初始节点。然后就可以进行常规的拓扑排序了：

代码

解法一：DFS

复杂度分析 设 n 为目录总数（题面约定目录 id 取值范围 [1, 200]，每个目录的子目录个数不超过 10）。

• 时间：读入并解析 n 行目录信息是 O(n)，其中每行的子目录列表至多 10 个元素，解析是常数级。DFS 从查询目录出发，其子树中每个目录恰好被递归访问一次、每条父子边恰好被走一次，边数不超过 10n，所以搜索部分是 O(n)。总时间复杂度为 O(n)。
• 空间：neighborTable 和 sizeTable 两个哈希表共存 n 个目录的信息，占 O(n)；DFS 递归栈在最坏情况（目录嵌套成一条链）下深度可达 O(n)。

边界与注意事项

• 目录 id 在 [1, 200] 内任意取值、不保证连续，所以邻接关系和目录大小都用哈希表存储，不能直接拿 id 当连续数组的下标用。
• 子目录列表可能为空：输入形如 "()"，parseChildren 对这种情况返回空列表，正好对应 DFS 的递归终止条件——没有子目录的目录，其总大小就是自身的文件大小。
• 累加顺序不能反：DFS 中必须先递归 dfs(childIdx)，让子目录的总大小在 sizeTable 中更新完毕，再把 sizeTable.get(childIdx) 加到当前目录上；如果先加后递归，加进来的只是子目录自身文件大小的半成品值，结果会偏小。
• 若查询的目录本身就是叶子目录，DFS 直接返回，输出即它自身的文件大小，这条路径也被上述终止条件自然覆盖。