1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// @Title: 统计最高分的节点数目 (Count Nodes With the Highest Score)
// @Author: 15816537946@163.com
// @Date: 2022-03-11 11:39:52
// @Runtime: 148 ms
// @Memory: 29.1 MB
func countHighestScoreNodes(parents []int) (ans int) {
    n := len(parents)
    children := make([][]int, n)
    for node := 1; node < n; node++ {
        p := parents[node]
        children[p] = append(children[p], node)
    }

    maxScore := 0
    var dfs func(int) int
    dfs = func(node int) int {
        score, size := 1, n-1
        for _, ch := range children[node] {
            sz := dfs(ch)
            score *= sz
            size -= sz
        }
        if node > 0 {
            score *= size
        }
        if score == maxScore {
            ans++
        } else if score > maxScore {
            maxScore = score
            ans = 1
        }
        return n - size
    }
    dfs(0)
    return
}