C++| DSU + Factorization | O(N*root(sum))
Hint: sum of all node values = (no. of component) * (value of component)\nThe problem is divided into two steps:\n1. find the value of component (say target). w
`Hint: sum of all node values = (no. of component) * (value of component)`\nThe problem is divided into two steps:\n1. find the value of component (say **target**). we will check for possible values.\n1. check if there are possible partitions with the target value, if yes find no. of Max component. Max edges removed = (max no. of component -1)\n\n* To find the value of component, we will use the Factorization method and check for all of those values.\n* To check the no. of max partition, I have used DSU. Now a question arrises, what is the criteria for the union of nodes and check the **Value of a component**? To do this, first find all node with degree 1 and push into the queue. Now union all these node with its direct parent. But before this, first check that if the value of component is equal to the **target** value. if it is, then insert its parent to a *set* ( which will mark this compenent as lock ). Also, avoid the union operation with any of the nodes whose component is locked.\n\n```\nclass Solution {\npublic:\n    int n;\n    int find(vector<int>& nums,int i){\n        if(nums[i]==-1) return i;\n        else return nums[i] = find(nums,nums[i]);\n    }\n    void union_(vector<int>& nums,vector<int>& sum,int x,int y){\n        int i = find(nums,x), j = find(nums,y);\n        if(i==j) return;\n        if(i<j) {nums[j] = i; sum[i]+=sum[j];}\n        else {nums[i] = j; sum[j]+=sum[i];}\n    }\n    int dfs(vector<int>& val,vector<int> deg,vector<vector<int>>& nums,int target){\n        queue<int> q;\n        vector<int> dp(n+1,-1), sum(n+1,-1);\n        for(int i = 0; i<n;++i) {\n            sum[i] = val[i];\n            if(deg[i]==1){\n                q.push(i); deg[i] = 0;\n            }\n        }\n        unordered_set<int> st;\n        while(!q.empty()){\n            int s = q.size();\n            while(s--){\n                int in = q.front(); q.pop();\n                int pt = find(dp,in); bool is = 1;\n                if(sum[pt]==target){ \n                    st.insert(find(dp,in)); is = 0;\n                }\n                if(sum[pt]>target) return 1;\n                for(int i = 0; i<nums[in].size();++i){\n                    int j = nums[in][i];\n                    int p = find(dp,j);\n                    if(deg[j] && st.find(p)==st.end()){\n                        deg[j]--;\n                        if(is) union_(dp,sum,in,j);\n                        if(deg[j]==1) q.push(j);\n                    }\n                }\n            }\n        }\n        int re = 0;\n        for(int i = 0; i<n;++i){\n            if(dp[i]==-1){\n                if(sum[i]==target) re++;\n                else return 1;\n            }\n        }\n        return re;\n    }\n    int componentValue(vector<int>& val, vector<vector<int>>& edges) {\n        n = val.size();\n        vector<int> deg(n+1,0);\n        vector<vector<int>> nums(n+1);\n        for(int i = 0; i<edges.size();++i){\n            deg[edges[i][0]]++; deg[edges[i][1]]++;\n            nums[edges[i][0]].push_back(edges[i][1]);\n            nums[edges[i][1]].push_back(edges[i][0]);\n        }\n        int sum = 0,re = 0;\n        for(int i = 0; i<n;++i) sum+=val[i];\n        for(int i = 1;i*i<=sum;++i){\n            if(sum%i==0){\n                re = max(re,dfs(val,deg,nums,i)-1);\n                re = max(re,dfs(val,deg,nums,sum/i)-1);\n            }\n        }\n        return re;\n    }\n};\n```\n***Comment for any queries. Upvote if it helps***
['C']