O(n) solution using simple tree traversal (C++) with explanation comments
\nclass Solution {\npublic:\n\n// first form a tree data structure to build your tree later in the q.\n\n    struct TreeNode\n    {\n        int val;\n        T
```\nclass Solution {\npublic:\n\n// first form a tree data structure to build your tree later in the q.\n\n    struct TreeNode\n    {\n        int val;\n        TreeNode *left=NULL;\n        TreeNode *right=NULL;\n    };\n    \n    map<int,long long> score;\n    long long maxScore=0;\n    \n\t// use this function to return the size, however, also keep updating the score simulatneously\n\t// store the score corresponding to each node in a map called score, declared above, also \n\t// keep a note of the largest score so far!\n\t\n    long long sizeHunt(TreeNode* node,int n)\n    {\n        if(!node) return 0;\n        if(!node->left&&!node->right) // incase of a leaf node\n        {\n            score[node->val]=n-1;\n            maxScore=max(maxScore,(long long) n-1);\n            return 1;\n        }\n        \n\t\t// incase it\'s a non-leaf node, you need to get the size of the left and right subtree and also, the nodes, other than that.\n\t\t\n        long long left=sizeHunt(node->left,n);\n        long long right=sizeHunt(node->right,n);\n        \n\t\t// remaining calculates the nodes other than the left and right subtrees.\n\t\t\n        long long rem=n-(left+right+1);\n        long long s=0;\n        if(left&&right) s=left*right;\n        else if(left) s=left;\n        else s=right;\n        \n        if(rem) s*=rem;\n        \n        score[node->val]=s;\n        maxScore=max(maxScore,score[node->val]);\n        \n\t\t// return the size of this subtree\n\t\t\n        return left+right+1;\n    }\n    \n    int countHighestScoreNodes(vector<int>& parents) {\n        int n=parents.size();\n        map<int,TreeNode*> mp;\n        \n\t\t// store the node correspoding to the node value in the map\n\t\t\n        for(int i=0;i<n;i++)\n        {\n            TreeNode* node=new TreeNode();\n            node->val=i;\n            mp[i]=node;\n        }\n        \n\t\t// use the parent array to assign the children to its parent.\n\t\t\n        for(int i=1;i<n;i++)\n        {\n            int p=parents[i];\n            TreeNode* prt=mp[p];\n            if(!prt->left) prt->left=mp[i];\n            else prt->right=mp[i];\n            \n            mp[p]=prt;\n        }\n        \n        TreeNode *root=mp[0];\n        \n        sizeHunt(root,n);\n        int ans=0;\n        \n\t\t// go through the whole score map to see how many nodes have got the maxScore.\n\t\t\n        for(auto it=score.begin();it!=score.end();it++)\n        {\n            if(it->second==maxScore) ans++;\n        }\n        \n        return ans;\n    }\n};\n\n```
[]