LeetCode 2049. 统计最高分的节点数目（DFS）

输入：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 ）。

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

class Solution {
    vector<vector<int>> g;
    vector<long long> score;
    long long ans = 0, n;
public:
    int countHighestScoreNodes(vector<int>& parents) {
        n = parents.size();
        g.resize(n);
        score.resize(n);
        for(int i = 1; i < n; ++i)
            g[parents[i]].push_back(i);
        vector<int> node(n, 0);
        dfs(0, node);
        dfs1(0, node);
        int ct = 0;
        for(auto s : score)
        {
            if(s == ans)
                ct++;
        }
        return ct;
    }
    int dfs(int x, vector<int>& node)
    {
        node[x]++;
        for(auto y : g[x])
            node[x] += dfs(y, node);
        return node[x];
    }
    void dfs1(int x, vector<int>& node)
    {
        for(auto y : g[x])
            dfs1(y, node);
        if(g[x].size()==0) score[x] = n-1;
        else if(g[x].size()==1)
        {
            int n1 = node[g[x][0]];
            score[x] = 1LL*n1*((n-1-n1)==0? 1 :(n-1-n1));
        }
        else
        {
            int n1 = node[g[x][0]];
            int n2 = node[g[x][1]];
            score[x] = 1LL*n1*n2*((n-1-n1-n2)==0? 1 : (n-1-n1-n2));
        }
        ans = max(ans, score[x]);
    }
};