题目描述

官方描述(中文)
2022/03/11每日一题

代码

class Solution {
public:
    /*
    执行结果：通过
    执行用时：256 ms, 在所有 C++ 提交中击败了41.30%的用户
    内存消耗：129.1 MB, 在所有 C++ 提交中击败了31.94%的用户
    通过测试用例：206 / 206
    */
    
    //对于每个节点，其分数就是(左子节点个数 * 右子节点个数 * (总结点数 - 当前节点为根节点的子树的节点数目))
    //每个乘数最小为1
    //求取每个节点下子节点个数
    using VecNode = vector<pair<int, vector<int>>>;
    int CountNum(int root, VecNode& nodes)
    {
        if (nodes[root].first >= 0)return nodes[root].first;
        auto& ch = nodes[root];
        ch.first = 1;

        for (auto iter : ch.second)
        {
            const auto num = CountNum(iter, nodes);
            ch.first += num;
        }
        return ch.first;
    }

    int countHighestScoreNodes(vector<int>& parents)
    {
        VecNode nodes(parents.size(), {-1, vector<int>()});
        for (int i = 1; i < parents.size(); ++i)
        {
            auto& node = nodes[parents[i]];
            node.second.push_back(i);
        }

        long long maxCount{ 0 };
        int res{ 0 };
        for (int i = 0; i < parents.size(); ++i)
        {
            const auto& node = nodes[i].second;
            int left = node.size() > 0 ? max(CountNum(node[0], nodes), 1) : 0;
            int right = node.size() > 1 ? max(CountNum(node[1], nodes), 1) : 0;

            int rootNum = max(CountNum(0, nodes) - left - right - 1, 1);

            auto maxCountTemp = (long long)max(1,left)*max(1, right)* rootNum;

            if (maxCountTemp > maxCount)
            {
                maxCount = maxCountTemp;
                res = 1;
            }
            else if (maxCountTemp == maxCount)
            {
                ++res;
            }
        }
        return res;
    }
};

Q.E.D.