README.md

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 表示一棵二叉树。

解法

第一步可以将 parents 数组转为相对好处理的邻接矩阵。

接下来，观察样例 1 中的 Removed 2，删除一个节点可能产生若干子树，或者整棵树除掉以该节点为根的子树后剩下的部分。

总结出规律后，递归处理即可。

Python3

class Solution:
    def countHighestScoreNodes(self, parents: List[int]) -> int:
        n, max_score, ans = len(parents), 0, 0
        g = [[] for _ in range(n)]
        for i in range(1, n):
            g[parents[i]].append(i)

        def dfs(cur: int) -> int:
            nonlocal max_score, ans
            size, score = 1, 1
            for c in g[cur]:
                s = dfs(c)
                size += s
                score *= s
            if cur > 0:
                score *= n - size
            if score > max_score:
                max_score = score
                ans = 1
            elif score == max_score:
                ans += 1
            return size

        dfs(0)
        return ans

Java

class Solution {

    private int n;
    private long maxScore;
    private int ans;
    private List<List<Integer>> graph;

    public int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        maxScore = 0;
        ans = 0;
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 1; i < n; i++) {
            graph.get(parents[i]).add(i);
        }
        dfs(0);
        return ans;
    }

    private int dfs(int cur) {
        int size = 1;
        long score = 1;
        for (int child : graph.get(cur)) {
            int s = dfs(child);
            size += s;
            score *= s;
        }
        if (cur > 0) {
            score *= n - size;
        }
        if (score > maxScore) {
            maxScore = score;
            ans = 1;
        } else if (score == maxScore) {
            ans++;
        }
        return size;
    }
}

TypeScript

function countHighestScoreNodes(parents: number[]): number {
    const n = parents.length;
    let edge = Array.from({ length: n }, (v, i) => []);
    for (let i = 0; i < n; i++) {
        const parent = parents[i];
        if (parent != -1) {
            edge[parent].push(i);
        }
    }

    let ans = 0;
    let max = 0;
    function dfs(idx: number): number {
        let size = 1,
            score = 1;
        for (let i = 0; i < edge[idx].length; i++) {
            const child = edge[idx][i];
            let childSize = dfs(child);
            size += childSize;
            score *= childSize;
        }
        if (idx > 0) {
            score *= n - size;
        }
        if (score > max) {
            max = score;
            ans = 1;
        } else if (score == max) {
            ans++;
        }
        return size;
    }
    dfs(0);
    return ans;
}

C++

class Solution {
public:
    int ans;
    long long maxScore;
    int n;

    int countHighestScoreNodes(vector<int>& parents) {
        ans = 0;
        maxScore = 0;
        n = parents.size();
        unordered_map<int, vector<int>> g;
        for (int i = 1; i < n; ++i) g[parents[i]].push_back(i);
        dfs(0, g);
        return ans;
    }

    int dfs(int u, unordered_map<int, vector<int>>& g) {
        int size = 1;
        long long score = 1;
        for (int v : g[u]) {
            int t = dfs(v, g);
            size += t;
            score *= t;
        }
        if (u > 0) score *= (n - size);
        if (score > maxScore) {
            maxScore = score;
            ans = 1;
        } else if (score == maxScore)
            ++ans;
        return size;
    }
};

Go

func countHighestScoreNodes(parents []int) int {
	n := len(parents)
	g := make([][]int, n)
	for i := 1; i < n; i++ {
		p := parents[i]
		g[p] = append(g[p], i)
	}
	maxScore, ans := 0, 0
	var dfs func(int) int
	dfs = func(u int) int {
		size, score := 1, 1
		for _, v := range g[u] {
			t := dfs(v)
			size += t
			score *= t
		}
		if u > 0 {
			score *= n - size
		}
		if score > maxScore {
			maxScore, ans = score, 1
		} else if score == maxScore {
			ans++
		}
		return size
	}
	dfs(0)
	return ans
}

...