题目描述
官方描述(中文)
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.