C++ | Single DFS O(n) |  Easy Explanation
\n# Approach\n Describe your approach to solving the problem. \n1. Need the sizes of all the subtrees (subordinate as well as above one) to calculate each node\
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Need the sizes of all the subtrees (subordinate as well as above one) to calculate each node\'s score.\n\n2. Calculate sizes of left & right subordinate subtree as we run the dfs function for the current node.\n\n3. Now to get the size of above tree, we simply can deduct the `sum of sizes of subordinate tree + 1 (current node)` from the total number of nodes(N).\nTherefore, `size of above subtree = N - sum - 1`.\n\n4. Calculate score and store it in `allScores` array while keeping track of `maxScore`.Return count of `maxScore` in `allScores`.\n\n---\n\n\n# Complexity\n- Time complexity: **O(n)** - *dfs, traversing parent, allScores array*\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: **O(n)** - *tree adjajency list, allScores array*\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n\n\n# Code\n```\nclass Solution {\npublic:\n    int N;\n    long maxScore = 0;\n    vector<long> allScores;\n\n    long dfs(int node,vector<vector<int>>& tree){\n        \n        long score = 1;\n        long sum = 0;\n        for(int v:tree[node]){\n            \n            long res = dfs(v,tree);\n            sum += res;\n            score *= res;\n        }\n        sum++; // added current\n        score *= (N-sum>0) ? N-sum : 1; // to check that score doesn\'t gets multiplied by 0 for root node\n        maxScore = max(maxScore,score);\n        allScores.push_back(score);\n\n        return sum;\n    }\n    int countHighestScoreNodes(vector<int>& parents) {\n        int n = parents.size();\n        N = n;\n        vector<vector<int>> tree(n);\n\n        for(int i=1; i<n; i++){\n\n            tree[parents[i]].push_back(i);\n        }\n\n        dfs(0,tree);\n        int cntOfMax = 0;\n\n        for(long& s: allScores){\n            if(s==maxScore) cntOfMax++;\n        }\n        return cntOfMax;\n    }\n};\n```
['Tree', 'Depth-First Search', 'Binary Tree', 'C++']