2049. 统计最高分的节点数目 : 建图 + DFS 运用题

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

题目描述

这是 LeetCode 上的 2049. 统计最高分的节点数目 ，难度为 中等。

Tag : 「图论」、「线性 DP」

给你一棵根节点为 $0$ 的 二叉树 ，它总共有 $n$ 个节点，节点编号为 $0$ 到 $n – 1$ 。

同时给你一个下标从 $0$ 开始的整数数组 $parents$ 表示这棵树，其中 $parents[i]$ 是节点 $i$ 的父节点。由于节点 $0$ 是根，所以 $parents[0] == -1$ 。

一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的 分数 。求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除 ，剩余部分是若干个 非空 子树，这个节点的 分数 为所有这些子树 大小的乘积 。

请你返回有 最高得分 节点的 数目 。

示例 1:

输入：parents = [-1,2,0,2,0]

输出：3

解释：
- 节点 0 的分数为：3 * 1 = 3
- 节点 1 的分数为：4 = 4
- 节点 2 的分数为：1 * 1 * 2 = 2
- 节点 3 的分数为：4 = 4
- 节点 4 的分数为：4 = 4
最高得分为 4 ，有三个节点得分为 4 （分别是节点 1，3 和 4 ）。
复制代码

示例 2：

输入：parents = [-1,2,0]

输出：2

解释：
- 节点 0 的分数为：2 = 2
- 节点 1 的分数为：2 = 2
- 节点 2 的分数为：1 * 1 = 1
最高分数为 2 ，有两个节点分数为 2 （分别为节点 0 和 1 ）。
复制代码

提示：

• $n == parents.length$
• $2 <= n <= 10^5$
• $parents[0] == -1$
• 对于 $i != 0$ ，有 $0 <= parents[i] <= n – 1$
• $parents$ 表示一棵二叉树。

建图 + DFS

为了更具有一般性，我们假定该树为多叉树。

由于题目给定的 parents 数组仅支持我们快速查找某个节点的父节点，为了方便遍历整棵树，我们先使用「邻接表」将图（树）建起来。

然后使用 DFS 预处理出 f 数组，其中 $f[i]$ 代表以节点 $i$ 为根节点的子树所包含的节点数量。

考虑如何计算「删除某个节点 $x$ 后，剩余连通块的数量，以及每个连通块的节点数量」，根据节点 $x$ 是否为根节点进行分情况讨论：

• 若 $x$ 为根节点，删除后的连通块的数量为「$x$ 的出边数量」，假定共有 $k$ 条出边，根据题目定义，对应的 大小 为各个连通块的节点数量乘积：