[Java] 35ms DFS, 95% + explanations
\nclass Solution {\n    /** Algorithm/Theory\n        1. An efficient first step is to build the tree. This way, we can post-order traverse it and determine the
```\nclass Solution {\n    /** Algorithm/Theory\n        1. An efficient first step is to build the tree. This way, we can post-order traverse it and determine the product of non-empty subtrees\n        2. Use a simple Node[] array to map node order/value to Node content.\n           set node[0] to be the parent.\n           loop from 1 to n and if the current node[i] is null, set it as new node. If the parent is null, initialize node[parent[i]].\n           set node[parent[i]].left or .right to node[i], depending if left or right is already set.\n        3. Continue post-order traversal. \n            - if on a leaf, that leaf will make a score of total -1. Check against the current highest score and set. Return 1 as that leaft has only 1 node\n            - if not on a leaf, apply post-oder to left and right.\n        4. After 3b) for each parent node, determine its number of nodes from its subtree: 1 + left + right.\n        6. Once 5 is done, determine the highest score that node will generate.\n           This will be Math.max(1, onLeft) * Math.max(1, onRight) * Math.max(1, (totalNodes - nrOfNodesFromSubtree)).\n           Basically we are multiplying the remaining 3 groups of nodes that are formed from the removal of that node (left, right, above).\n           Pay attention to multiply with 1 (not with 0). The root will have no "above" nodes so total - nodesOnSubtree will return 0.\n    */\n   public int countHighestScoreNodes(int[] parents) {\n        Node[] nodes = buildTree(parents);\n        long[] highestScore = {0,0};\n        countHighestScore(nodes[0], highestScore, parents.length);\n        return (int)highestScore[1];\n    }\n\n    private int countHighestScore(Node node, long[] highestScore, int total) {\n        if (node != null) {\n            if (node.left == null && node.right == null) {\n                // a leaf will have 1 node under(itself) and will produce a total nodes - 1 score.\n                if (highestScore[0] == total - 1) {\n                    highestScore[1]++;\n                } else if (highestScore[0] < total - 1) {\n                    highestScore[0] = total - 1;\n                    highestScore[1] = 1;\n                }\n                return 1;\n            } else {\n                // apply post-order and see how many nodes are left and right\n                int onLeft = countHighestScore(node.left, highestScore, total);\n                int onRight = countHighestScore(node.right, highestScore, total);\n                int totalSubtree = onLeft + onRight + 1;\n                // if left or right is null, replace it with 1, multiplication by 1\n                long possibleScore = (long) (Math.max(1, onLeft)) * Math.max(onRight, 1)\n                        * Math.max(1, total - totalSubtree);\n                if (highestScore[0] == possibleScore) {\n                    highestScore[1]++;\n                } else if (highestScore[0] < possibleScore) {\n                    highestScore[0] = possibleScore;\n                    highestScore[1] = 1;\n                }\n                return totalSubtree;\n            }\n        }\n        return 0;\n    }\n\n    private Node[] buildTree(int[] parents) {\n        Node[] nodes = new Node[parents.length];\n        nodes[0] = new Node();\n        for (int i = 1; i < parents.length; i++) {\n            // create current node\n            if (nodes[i] == null) {\n                nodes[i] = new Node();\n            }\n            // create parent node\n            if (nodes[parents[i]] == null) {\n                nodes[parents[i]] = new Node();\n            }\n            // link parent node left or right to this child node.\n            if (nodes[parents[i]].left == null) {\n                nodes[parents[i]].left = nodes[i];\n            } else {\n                nodes[parents[i]].right = nodes[i];\n            }\n        }\n        return nodes;\n    }\n\n    private static class Node {\n        Node left;\n        Node right;\n    }\n}\n```
['Depth-First Search', 'Java']