Dynamic Programming On Graphs
I used dp on trees to solve this problem.\nThe concept is simple. \nFirst you calculate size of each subtree for every node. Here dp on trees is applied for tha
I used dp on trees to solve this problem.\nThe concept is simple. \nFirst you calculate size of each subtree for every node. Here dp on trees is applied for that. Size of subtrees added and +1 to get total size of that current node.\nTo calculate score for current node, you subtract size of root node subtracted with size of current node and that is multiplied with sizes of subtree nodes.\n\n        \n\t\tint countHighestScoreNodes(vector<int>& parent) {\n        \n        int n=parent.size();\n        vector<vector<int>> adj(n);\n        for(int i=1;i<n;i++)\n        {\n            adj[parent[i]].push_back(i);\n        }\n        vector<ll> sz(n,0),score(n,0);\n        dfs(0,adj,sz);\n        ll max_score=INT_MIN;\n        ll s=1;\n        for(auto j: adj[0])\n            s*=sz[j];\n        score[0]=s;\n        for(int i=1;i<n;i++)\n        {\n            s=1;\n            s*=(sz[0]-sz[i]);\n            for(auto j: adj[i])\n            {\n                s*=sz[j];\n            }\n            score[i]=s;\n          //  cout<<score[i]<<" ";\n        }\n        int count=0;\n        max_score=*max_element(score.begin(),score.end());\n        for(auto i: score)\n        {\n            if(max_score==i)\n                count++;\n        }\n        return count;\n        \n    }\n    void dfs(int i, vector<vector<int>> &adj, vector<ll> &sz)\n    {\n        sz[i]++;\n        for(auto j: adj[i])\n        {\n            dfs(j,adj,sz);\n            sz[i]+=sz[j];\n        }\n      //  cout<<sz[i]<<endl;\n    }
['Dynamic Programming', 'Tree', 'Depth-First Search', 'Graph']