C++ DFS solution
DFS solution. The first one uses a few maps to manage the countings. The second solution uses global variable and does the comparison in the DFS. \n\nSolution 1
DFS solution. The first one uses a few maps to manage the countings. The second solution uses global variable and does the comparison in the DFS. \n\nSolution 1\n```\nclass Solution {\npublic:\n    int countHighestScoreNodes(vector<int>& parents) {\n        \n        unordered_map<int, vector<int>> graph;\n        \n        for (int i = 0; i < parents.size(); ++i)\n        {\n            int p = parents[i];\n            if (graph.find(p) != graph.end())\n            {\n                graph[p].push_back(i);\n            }\n            else\n            {\n                vector<int> v { i };\n                graph[p] = v;\n            }\n        }\n        \n        unordered_map<int, long long> productMap;\n        unordered_map<int, int> totalMap;\n        \n        int sum = dfs(-1, graph, productMap, totalMap);\n        \n        long long max = 0;\n        int count = 0;\n        long long product = 1;\n        \n        for (int i = 0; i < parents.size(); ++i)\n        {\n            product = 1;\n            \n            if (i == 0)\n            {\n                product = productMap[0];\n            }\n            else\n            {\n                product = (sum - totalMap[i] - 1) * productMap[i];\n            }\n            \n            if (product > max)\n            {\n                max = product;\n                count = 1;\n            }\n            else if (product == max)\n            {\n                ++count;\n            }\n        }\n        return count;\n    }\n    \n    \n    int dfs(int node, unordered_map<int, vector<int>> &graph, unordered_map<int, long long> &productMap, \n            unordered_map<int, int> &totalMap)\n    {\n        int sum = 1;\n        long long product = 1;\n        \n        if (graph.find(node) == graph.end())\n        {\n            totalMap[node] = sum;\n            productMap[node] = product;\n            \n            return sum;\n        }\n        \n        vector<int> nodes = graph[node];\n        \n        for (int &n : nodes)\n        {\n            int num = dfs(n, graph, productMap, totalMap);\n            \n            sum += num;\n            product *= num;\n        }\n        \n        totalMap[node] = sum;\n        productMap[node] = product;\n        \n        return sum;\n    }\n};\n```\n\nSolution 2\n```\nclass Solution {\n    \n    long max = 0;\n    int count = 0;\n    \npublic:\n    int countHighestScoreNodes(vector<int>& parents) {\n        \n        unordered_map<int, vector<int>> graph;\n        \n        for (int i = 0; i < parents.size(); ++i)\n        {\n            int p = parents[i];\n            if (graph.find(p) != graph.end())\n            {\n                graph[p].push_back(i);\n            }\n            else\n            {\n                vector<int> v { i };\n                graph[p] = v;\n            }\n        }\n        \n        int sum = parents.size();\n        \n        dfs(0, graph, sum);\n        \n        return count;\n    }\n    \n    \n    int dfs(int node, unordered_map<int, vector<int>> &graph, int &sum)\n    {\n        long product = 1;\n        int total = 1;\n        \n        if (graph.find(node) == graph.end())\n        {\n            product = (long)(sum - 1);\n            \n            if (product > max)\n            {\n                max = product;\n                count = 1;\n            }\n            else if (product == max)\n            {\n                ++count;\n            }\n            return total;\n        }\n        \n        vector<int> nodes = graph[node];\n        \n        for (int &n : nodes)\n        {\n            int num = dfs(n, graph, sum);\n            \n            product *= num;\n            total += num;\n        }\n        \n        if (node != 0)\n        {\n            product *= (sum - total);\n        }\n        \n        if (product > max)\n        {\n            max = product;\n            count = 1;\n        }\n        else if (product == max)\n        {\n            ++count;\n        }\n        \n        return total;\n    }\n};\n```
[]