P3514. 寻找最富裕的小家庭

解题思路

常规搜索解法

题目所给的数据形式，非常容易想到转化为邻接表来储存数据。 另外，由于数据所给的编号是从 1 开始 的，为了方便后续对应上财富列表的索引（从 0 开始），可以把 -1 之后的结果 作为编号来储存。

另外，由于本题的输入没有告知根节点 root，我们需要根据输入的 n-1 条边 来找到根节点。 根节点 root 存在特点：根节点 root 不是任何一个节点的子节点。因此，我们可以根据 n-1 条边中的所有子节点，反推出唯一那个不是子节点的节点，即为根节点。具体代码如下：

剩下的就是常规的 DFS 和 BFS 过程了。由于本题所给数据是树型结构（有向无环图），不会出现同一个节点多次进入的情况，因此无需额外使用 check_list 来维护节点重复进入。

对于 DFS 而言，核心函数为：

对于 BFS 而言，核心过程为：

可以发现都涉及相似的过程：

• 考虑当前小家庭的父节点 i
• 初始化当前小家庭的总财富值 little_family_sum = money_list[i]
• 考虑 i 的所有子节点 child
• 对 child 进行递归（DFS） / 将 child 加入队列中（BFS）
• 根据子节点的财富 money_list[ch]，更新当前小家庭的总财富值 little_family_sum
• 基于当前小家庭的总财富值 little_family_sum，更新全局的答案 ans

无需搜索的简单解法

另外，本题还存在一种非常简单的解法，无需进行 DFS/BFS 搜索。 由于每一个小家庭仅由父节点和其子节点构成，这里的对应关系可以从边的对应关系中直接得到。 在拿到一条边 (fa, ch) 的时候，实际上我们可以马上知道父节点 fa 和子节点 ch 对应的财富 money_list[fa] 和 money_list[ch]。

仅需额外构建一个列表 little_family_list，little_family_list[i] 表示以 i 为父节点的小家庭的财富。 初始化 little_family_list[i] = money_list[i]（这样才能避免父节点的重复计算），然后对于所有的边 (fa, ch)，将 fa 的孩子 ch 的财富加入到这个小家庭中（只往小家庭中加入子节点），即 little_family_list[fa] += money_list[ch]。 最后找到 little_family_list 中的最大值即为答案。整体的核心代码如下：

复杂度分析 设 n 为家庭成员（节点）的数量，输入共有 n-1 条父子边。

• 建图阶段：读入 n 个财富值与 n-1 条边，用哈希表 neighborDic 建邻接表，并把所有子节点放进 childrenSet，这一步是 O(n)。
• 找根阶段：从 0 到 n-1 扫一遍，找出不在 childrenSet 中的节点作为根，最坏 O(n)。
• DFS 阶段：从根出发递归，每个节点恰好被访问一次；访问节点 i 时内层循环遍历它的所有子节点，全部节点的子节点数加起来正好是 n-1 条边，所以整个 DFS 是 O(n)。

综上时间复杂度为 O(n)，瓶颈就是对 n 个节点、n-1 条边的一次完整遍历。空间复杂度 O(n)：邻接表与 childrenSet 各存 O(n) 个元素，DFS 递归栈深度等于树高，最坏（链状树）为 O(n)。