pure C
Intuition\nMy first thought was to use DFS in a post-order traversal manner to compute the number of nodes in each subtree.\nBy traversing each node\'s left and
# Intuition\nMy first thought was to use DFS in a post-order traversal manner to compute the number of nodes in each subtree.\nBy traversing each node\'s left and right children, we can calculate the number of nodes in the left and right subtrees, then compute the "score" using the below formula:\n```\nscore = left * right * (total - left - right - 1)\n```\nThe term ```total - left - right - 1``` represents the remaining nodes outside of the current subtree\n\n\n# Approach\nUse two arrays leftChild and rightChild:\n>to represent the left and right children of each node by parsing the parents array.\n\nA DFS function that:\n> 1. Return the size of the subtrees.\n> 2. Calculate the score for the current node using the formula: left * right * (total - left - right - 1).\n> 3. Track the maximum score and count how many nodes achieve this maximum score.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$ (ignore constant factors)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```c []\nint dfs(int node, int *leftChild, int *rightChild, int totalNodes, long *maxScore, int *maxCount) {\n    if (node == -1) return 0;\n\n    int left = dfs(leftChild[node], leftChild, rightChild, totalNodes, maxScore, maxCount);\n    int right = dfs(rightChild[node], leftChild, rightChild, totalNodes, maxScore, maxCount);\n\n    long score = 1;\n    int subtreeSize = left + right + 1;\n\n    if (left > 0) score *= left;\n    if (right > 0) score *= right;\n    if (totalNodes - subtreeSize > 0) score *= (totalNodes - subtreeSize);;\n\n    if (score > *maxScore) {\n        *maxCount = 1;\n        *maxScore = score;\n    } else if (score == *maxScore){\n        (*maxCount) += 1;\n    }\n\n    return subtreeSize;\n}\n\nint countHighestScoreNodes(int* parents, int parentsSize) {\n    int totalNodes = parentsSize;\n    long maxScore = 0, maxCount = 0;\n\n    int *leftChild = malloc(sizeof(int) * parentsSize);\n    int *rightChild = malloc(sizeof(int) * parentsSize);\n\n    // init\n    for (int i = 0; i < parentsSize; ++i) {\n        leftChild[i] = -1;\n        rightChild[i] = -1;\n    }\n\n    // construct the left and right child\n    for (int i = 1; i < parentsSize; ++i) {\n        int parent = parents[i];\n\n        if (leftChild[parent] == -1) {\n            leftChild[parent] = i;\n        } else {\n            rightChild[parent] = i;\n        }\n    }\n\n    dfs(0, leftChild, rightChild, totalNodes, &maxScore, &maxCount);\n    \n    free(leftChild);\n    free(rightChild);\n\n    return maxCount;\n}\n```
['Depth-First Search', 'C', 'Binary Tree', 'Counting']