Subtree size  | Adjacency List
Intuition\n Describe your first thoughts on how to solve this problem. \nScore is product of subtree sizes so we should have a easier way to find subtree size w
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nScore is product of subtree sizes so we should have a easier way to find subtree size when each of node is removed in constant time.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFind subtree size of each node. (If you don\'t know search on cp algo or CodeNCode channel).\n\nTo find the answer we have to check score of each node removal and maintain max score.\n\nWhen a node is removed we will have atmost 3 different trees. \nTrees formed from left and right subtrees of current node , and another tree from parent node . \n\nlong long x = max(n-subtreesize[i],1); Gives subtree size for 3rd option . To understand this try checking on different nodes \n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int>subtreesize;\n    vector<int>vis;\n    int dfs(int node,vector<int> adj[], int csize)\n    {\n        vis[node]=1;\n        subtreesize[node] = csize;\n        for(auto child : adj[node])\n        {\n            if(vis[child]==0)\n            {\n                subtreesize[node] += dfs(child,adj,1);\n            }\n        }\n        return subtreesize[node];\n\n    }\n    int countHighestScoreNodes(vector<int>& parents)\n    {\n       int n = parents.size();\n       vector<int>adj[n+1];\n       for(int i=1;i<n;i++)\n       {\n            adj[parents[i]].push_back(i);\n            adj[i].push_back(parents[i]);\n       }\n       subtreesize.resize(n+2,0);\n       vis.resize(n+2,0);\n        dfs(0,adj,1);\n\n        for(int i=0;i<n;i++)\n        {\n            cout<<subtreesize[i]<<" ";\n        }\n        long long score = 0;\n        int ans = 0;\n        for(int i=0;i<n;i++)\n        {\n            long long x = max(n-subtreesize[i],1);\n\n            for(auto child : adj[i])\n            {\n                if(child == parents[i])continue;\n                x *= subtreesize[child];\n            }\n            if(x>score)\n            {\n                score = x;\n                ans =1; \n            }\n            else if(x==score)\n            {\n                ans++;\n            }\n        }\n        return ans;\n\n    }\n};\n```
['C++']