题目重点：Uber VO Folder System 面经给出 add folder 与 print(id) 例子。建立父指针与根可达性索引，处理孤儿节点，并指出题目重复 root ID=0 的歧义。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 可运行训练契约要求 folder ID 唯一，每个非根节点至多一个父节点，给定明确的 rootId；add(id,childIds,name) 可先存关系后验证完整图。
- print(id) 若节点从 rootId 可达，返回根到该节点的名字链；不可达返回空字符串。题目示例中 5 是孤儿，print(5) 应为空。
- 题目同时写 [0,...,folderR1] 与 [0,...,folderR2]，违反 ID 唯一。如果两个根确实都用 ID 0，必须先要求额外的根实例 ID 或覆盖规则；本文不替题目猜测。
解题路线
- 每条 add 记录节点名称与孩子 ID。构建 child→parent 映射时，发现同一 child 多父或相同 ID 名称冲突就标记输入歧义，不悄悄选择最后一条。
- 从指定 rootId 做 DFS/BFS 标记可达节点，并可记录 parent。查询 id 若不在可达集合直接返回空串；否则沿 parent 指针回根，逆序拼名字。
- 若查询量大且图静态，可在一次根遍历中预计算每个 ID 的父指针与深度；完整路径字符串如逐节点缓存，最坏空间会升到所有路径总长度。
手动走一遍
一致部分：根 folderR1(ID 0)→folder8(ID 8)→folder9(ID 9)，print(9) 得 folderR1→folder8→folder9。folder5(ID 5) 没有通往根的链，返回空串。若再加入另一个 ID 0 名为 folderR2，训练实现报输入冲突而非随意覆盖。
规模与取舍
建索引和根可达性遍历 O(V+E) 时间、O(V+E) 空间；单次 print 路径长度 h，时间/输出空间 O(h)。若每次查询都重扫整张图，会退化到 O(V+E) 每次。
易错点与追问
容易失分的边界
- 从任意节点沿孩子边 DFS 找到 9 不能证明它属于指定根；先确定根可达性。
- 同一 ID=0 对应 folderR1 与 folderR2 是题目内在歧义，不能用字典最后写入覆盖来制造一个看似确定的答案。
- 若输入可能成环，遍历需 visited 并报错；循环 parent 链会导致 print 无限循环。
继续深挖
- 若要支持同名不同 ID 的文件夹，按 ID 建图仍可正确输出名称路径；若要求唯一文本路径，可能需附带 ID 防止歧义。
- 动态 move(folder,newParent) 需检查不会把节点移到其后代之下，并维护 parent、可达性与缓存失效。
