Question

2049. 统计最高分的节点数目

English Version

题目描述

给你一棵根节点为 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 <= 105
• parents[0] == -1
• 对于 i != 0 ，有 0 <= parents[i] <= n - 1
• parents 表示一棵二叉树。

解法

方法一：DFS

我们先根据给定的父节点数组 parents 构建图 $g$，其中 $g[i]$ 表示节点 $i$ 的所有子节点。定义变量 $ans$ 表示最高得分的节点数目，变量 $mx$ 表示最高得分。

然后，我们设计一个函数 $dfs(i, fa)$，它的作用是计算节点 $i$ 的分数，并返回以节点 $i$ 为根的子树的节点数目。

函数 $dfs(i, fa)$ 的计算过程如下：

我们首先初始化变量 $cnt = 1$，表示以节点 $i$ 为根的子树的节点数目；变量 $score = 1$，表示以节点 $i$ 初始分数。

接下来，我们遍历节点 $i$ 的所有子节点 $j$，如果 $j$ 不是节点 $i$ 的父节点 $fa$，那么我们递归调用 $dfs(j, i)$，并将返回值累乘到 $score$ 中，同时将返回值累加到 $cnt$ 中。

遍历完子节点后，如果 $n - cnt > 0$，那么我们将 $n - cnt$ 累乘到 $score$ 中。

然后，我们判断 $mx$ 是否小于 $score$，如果小于，那么我们将 $mx$ 更新为 $score$，并将 $ans$ 更新为 $1$；如果等于，那么我们将 $ans$ 更新为 $ans + 1$。

最后，我们返回 $cnt$。

最终，我们调用 $dfs(0, -1)$，并返回 $ans$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是节点数目。

class Solution:
  def countHighestScoreNodes(self, parents: List[int]) -> int:
    def dfs(i: int, fa: int):
      cnt = score = 1
      for j in g[i]:
        if j != fa:
          t = dfs(j, i)
          score *= t
          cnt += t
      if n - cnt:
        score *= n - cnt
      nonlocal ans, mx
      if mx < score:
        mx = score
        ans = 1
      elif mx == score:
        ans += 1
      return cnt

    n = len(parents)
    g = [[] for _ in range(n)]
    for i in range(1, n):
      g[parents[i]].append(i)
    ans = mx = 0
    dfs(0, -1)
    return ans

class Solution {
  private List<Integer>[] g;
  private int ans;
  private long mx;
  private int n;

  public int countHighestScoreNodes(int[] parents) {
    n = parents.length;
    g = new List[n];
    Arrays.setAll(g, i -> new ArrayList<>());
    for (int i = 1; i < n; ++i) {
      g[parents[i]].add(i);
    }
    dfs(0, -1);
    return ans;
  }

  private int dfs(int i, int fa) {
    int cnt = 1;
    long score = 1;
    for (int j : g[i]) {
      if (j != fa) {
        int t = dfs(j, i);
        cnt += t;
        score *= t;
      }
    }
    if (n - cnt > 0) {
      score *= n - cnt;
    }
    if (mx < score) {
      mx = score;
      ans = 1;
    } else if (mx == score) {
      ++ans;
    }
    return cnt;
  }
}

class Solution {
public:
  int countHighestScoreNodes(vector<int>& parents) {
    int n = parents.size();
    vector<int> g[n];
    for (int i = 1; i < n; ++i) {
      g[parents[i]].push_back(i);
    }
    int ans = 0;
    long long mx = 0;
    function<int(int, int)> dfs = [&](int i, int fa) {
      long long score = 1;
      int cnt = 1;
      for (int j : g[i]) {
        if (j != fa) {
          int t = dfs(j, i);
          cnt += t;
          score *= t;
        }
      }
      if (n - cnt) {
        score *= n - cnt;
      }
      if (mx < score) {
        mx = score;
        ans = 1;
      } else if (mx == score) {
        ++ans;
      }
      return cnt;
    };
    dfs(0, -1);
    return ans;
  }
};

func countHighestScoreNodes(parents []int) (ans int) {
  n := len(parents)
  g := make([][]int, n)
  for i := 1; i < n; i++ {
    g[parents[i]] = append(g[parents[i]], i)
  }
  mx := 0
  var dfs func(i, fa int) int
  dfs = func(i, fa int) int {
    cnt, score := 1, 1
    for _, j := range g[i] {
      if j != fa {
        t := dfs(j, i)
        cnt += t
        score *= t
      }
    }
    if n-cnt > 0 {
      score *= n - cnt
    }
    if mx < score {
      mx = score
      ans = 1
    } else if mx == score {
      ans++
    }
    return cnt
  }
  dfs(0, -1)
  return
}

function countHighestScoreNodes(parents: number[]): number {
  const n = parents.length;
  const g: number[][] = Array.from({ length: n }, () => []);
  for (let i = 1; i < n; i++) {
    g[parents[i]].push(i);
  }
  let [ans, mx] = [0, 0];
  const dfs = (i: number, fa: number): number => {
    let [cnt, score] = [1, 1];
    for (const j of g[i]) {
      if (j !== fa) {
        const t = dfs(j, i);
        cnt += t;
        score *= t;
      }
    }
    if (n - cnt) {
      score *= n - cnt;
    }
    if (mx < score) {
      mx = score;
      ans = 1;
    } else if (mx === score) {
      ans++;
    }
    return cnt;
  };
  dfs(0, -1);
  return ans;
}

public class Solution {
  private List<int>[] g;
  private int ans;
  private long mx;
  private int n;

  public int CountHighestScoreNodes(int[] parents) {
    n = parents.Length;
    g = new List<int>[n];
    for (int i = 0; i < n; ++i) {
      g[i] = new List<int>();
    }
    for (int i = 1; i < n; ++i) {
      g[parents[i]].Add(i);
    }

    Dfs(0, -1);
    return ans;
  }

  private int Dfs(int i, int fa) {
    int cnt = 1;
    long score = 1;

    foreach (int j in g[i]) {
      if (j != fa) {
        int t = Dfs(j, i);
        cnt += t;
        score *= t;
      }
    }

    if (n - cnt > 0) {
      score *= n - cnt;
    }

    if (mx < score) {
      mx = score;
      ans = 1;
    } else if (mx == score) {
      ++ans;
    }

    return cnt;
  }
}