C# Tree Traversal and Subtree Size Calculation Solution using DFS
Intuition\n Describe your first thoughts on how to solve this problem. The problem can be approached by leveraging tree traversal techniques, specifically DFS, 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->The problem can be approached by leveraging tree traversal techniques, specifically DFS, to gather essential information about the tree structure, such as subtree sizes. This data allows simulating the removal of each node efficiently, which is the core requirement to compute scores. The solution is built upon a clear understanding of tree properties and the use of DFS as a powerful tool for recursive calculations, making it a systematic and logical approach to solving the problem. The main idea is to transform the problem into manageable parts: calculate subtree sizes, compute scores, and compare scores to identify the nodes with the maximum score.\n___\n\n# Approach\n<!-- Describe your approach to solving the problem. -->//  Tree Construction: The adjacency list tree is created to store the child nodes for each parent.\n//  DFS to Calculate Subtree Sizes: The DFS function computes the size of each subtree rooted at a given \n//  node, which is crucial for score calculations.\n//  Score Calculation:\n//  *For each node, compute the product of the sizes of its child subtrees.\n//  *Multiply this product by the size of the remaining nodes (if any).\n//  *Update the maximum score and count of nodes achieving this score.\n//  Result: the function returns the count of nodes with the highest score.\n___\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->O(n), where \'n\' is the number of nodes.\n___\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(n).\n___\n\n# Code\n```csharp []\nusing System;\nusing System.Collections.Generic;\n\npublic class Solution {\n    public int CountHighestScoreNodes(int[] parents) {\n        int n = parents.Length;\n        \n        // Create an adjacency list to represent the tree\n        List<int>[] tree = new List<int>[n];\n        for (int i = 0; i < n; i++) {\n            tree[i] = new List<int>();\n        }\n        \n        // Build the tree structure\n        for (int i = 1; i < n; i++) {\n            tree[parents[i]].Add(i);\n        }\n        \n        // Array to store subtree sizes\n        int[] subtreeSizes = new int[n];\n        \n        // Use DFS to calculate the size of each subtree\n        DFS(0, tree, subtreeSizes);\n        \n        long maxScore = 0;\n        int count = 0;\n        \n        // Calculate the score for each node\n        for (int i = 0; i < n; i++) {\n            long score = 1;\n            int remainingNodes = n - 1; // Total nodes excluding the current node\n            \n            // Multiply the sizes of each child subtree\n            foreach (int child in tree[i]) {\n                score *= subtreeSizes[child];\n                remainingNodes -= subtreeSizes[child];\n            }\n            \n            // Multiply by the size of the remaining tree if it\'s not empty\n            if (remainingNodes > 0) {\n                score *= remainingNodes;\n            }\n            \n            // Update maxScore and count\n            if (score > maxScore) {\n                maxScore = score;\n                count = 1;\n            } else if (score == maxScore) {\n                count++;\n            }\n        }\n        \n        return count;\n    }\n    \n    // DFS to calculate the size of each subtree\n    private int DFS(int node, List<int>[] tree, int[] subtreeSizes) {\n        int size = 1; // Counting the current node itself\n        foreach (int child in tree[node]) {\n            size += DFS(child, tree, subtreeSizes);\n        }\n        subtreeSizes[node] = size;\n        return size;\n    }\n}\n```
['Array', 'Tree', 'Depth-First Search', 'C#']