今天又做了一道有趣的题，或许可以用在树的切割上？

解题思路

1. 观察题目我们可以发现，节点分数的计算方法：
   score = (根节点子树大小 - 本节点子树大小) * 本节点左子树大小 * 本节点右子树大小

2. 问题就转变为如何求出每个节点子树大小，这一点利用DFS递归的特性会比较容易求出：
   $当前子树大小=左子树大小+右子树大小$
   注意到本题我们无需手动定义二叉树节点并构建二叉树：
   通过入参parents，我们可以求出每个节点对应的子节点，记为children，children的下标表示节点，值表示节点的子节点（们）（这很容易推广到N叉树的情况）。得到children，我们就确定了使用DFS递归遍历时，当前节点node往更深一层的前进方向，使得我们得以完成DFS的编写。

3. 求出所有子树大小subTreeSize后，通过遍历subTreeSize并计算第1点介绍的公式，就很容易得到题目所求，注意要求的是不是最高分数，而是最高得分节点数。

代码

func dfs(node int, children *[][]int, subTreeSize *[]int) int{
    if (*subTreeSize)[node]>0{
        return (*subTreeSize)[node]
    }

    sum := 1
    for _, next_node := range (*children)[node]{
        sum += dfs(next_node, children, subTreeSize)
    }

    (*subTreeSize)[node] = sum
    return (*subTreeSize)[node]
}

func countHighestScoreNodes(parents []int) int {
    // （总节点个数-本子树节点个数）* 左子树节点个数 * 右子树节点个数
    children := make([][]int, len(parents), len(parents))
    for i, p := range parents{
        if p!= -1{
            children[p] = append(children[p], i) 
        }
    }

    // 求每个子树大小
    subTreeSize := make([]int, len(parents), len(parents))
    dfs(0, &children, &subTreeSize)

    // 每个节点作为删除节点时的大小
    maxScore := 0
    maxCount := 0
    score := 1
    for node, size := range subTreeSize{
        score = 1
        if node > 0{
            score = subTreeSize[0] - size
        }
        for _, c := range children[node]{
            score *= subTreeSize[c]
        }
        if score > maxScore{
            maxScore = score
            maxCount = 1
        }else if score == maxScore{
            maxCount += 1
        }
    }

    return maxCount
}