C++ || SOLUTION || DFS
Optimized Approach\n\nclass Solution {\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        int sum=0;\n        // sum of 
# Optimized Approach\n```\nclass Solution {\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        int sum=0;\n        // sum of all values which are associated with every node\n        for(auto num: nums) // TC: O(n)\n         sum+=num;\n         \n       int n=nums.size();  // TC: O(n)\n       vector<int>inEdge(n,0);  // SC, TC: O(n)\n        vector<vector<int>>adjList(n,vector<int>()); // TC,SC: O(n)\n        for(auto it: edges)\n        {\n            adjList[it[0]].push_back(it[1]);\n            adjList[it[1]].push_back(it[0]);\n            inEdge[it[0]]++;\n            inEdge[it[1]]++;\n        }\n       \n       // deciding the root of tree\n        int root=0;\n        // TC: O(n)\n        for(int i=0;i<n;i++)\n         if(inEdge[i]==1)\n          {root=i;\n           break;}\n      \n\n      // making list of divisor of sum, so that we can find out that in what numbers of component can we divide the whole tree\n       vector<int>divisor; // SC: O(sum)\n       int i=1;\n       while(i<=sum) // TC: O(sum)\n       {\n           if(sum%i==0)\n            divisor.push_back(i);\n            i++;\n       }\n\n       \n       // use dfs \n     // TC: O(sum*(V+E))\n     // SC: O(sum(V+E+n))\n       for(auto it=divisor.rbegin();it!=divisor.rend();it++)\n         {   int cnt=0;\n         vector<int>visited(n,0);\n    dfs(adjList,nums,root,sum/(*it),cnt,visited);\n            // if number of component is equal to divisor\n              if(cnt==*it)\n              return *it-1; // no. of component = no. of deleted edge+1\n           \n         }\n  \n         return 0;\n        \n    }\n  int dfs(vector<vector<int>>&adjList,vector<int>&nums,int node,int target,int &cnt,vector<int>&visited)\n  {\n      // mark as visited\n      visited[node]=1;\n       \n      int load=0;\n     // traverse over neighbors\n     for(auto adjNode: adjList[node])\n     {\n      if(!visited[adjNode])\n       load+=dfs(adjList,nums,adjNode,target,cnt,visited);   \n     }\n    load+=nums[node];\n    if(load==target)\n     {cnt++;\n      load=0;}\n     return load;\n  }\n};\n```\n\n# Brute Force Approach\n```\nclass Solution {\n    private:\n    int ans=0;\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        vector<int>consider(edges.size(),1);\n         fun(nums,edges,0,consider);\n         return ans;\n    }\n    void fun(vector<int>&nums, vector<vector<int>>&edges,int index,vector<int>&consider)\n    {\n        // cout<<"index:"<<index<<"    ans:"<<ans<<endl;\n        ans=max(makeComp(nums,edges,consider),ans);\n        //  cout<<endl;\n        if(index==edges.size())\n           return;\n\n        // let delete this\n         // pre-calculation\n         consider[index]=0;\n         fun(nums,edges,index+1,consider);\n         // post-calculation\n         consider[index]=1;\n        \n        // not delete this\n        fun(nums,edges,index+1,consider);\n         \n    }\n    int find(vector<int>&dsuf,int v)\n    {\n        if(dsuf[v]<0)\n         return v;\n        return dsuf[v]=find(dsuf,dsuf[v]);\n    }\n    void Union(vector<int>&dsuf,int from ,int to)\n    {\n        from=find(dsuf,from);\n        to=find(dsuf,to);\n        if(from!=to)\n        {\n            if(dsuf[from]<dsuf[to])\n            {\n                dsuf[from]+=dsuf[to];\n                dsuf[to]=from;\n            }\n            else\n            {\n                dsuf[to]+=dsuf[from];\n                dsuf[from]=to;\n            }\n        }\n    }\n  int makeComp(vector<int>&nums, vector<vector<int>>&edges,vector<int>&consider)\n    {  vector<int>dsuf(nums.size(),-1);\n    int cnt=0;\n        for(int i=0;i<consider.size();i++)\n         {\n             if(consider[i])\n            {\n                Union(dsuf,edges[i][0],edges[i][1]);\n            }\n            else\n              cnt++;\n         }\n        //  for(int i=0;i<dsuf.size();i++)\n        //   cout<<"node:"<<i<<"   parent:"<<dsuf[i]<<endl;\n\n         unordered_map<int,int>mp;\n         for(int i=0;i<dsuf.size();i++)\n         {\n             if(dsuf[i]<0)\n             {\n                mp[i]+=nums[i];\n             }\n             else\n             mp[dsuf[i]]+=nums[i];\n         }\n        unordered_set<int>st;\n        for(auto p:mp)\n        \n             st.insert(p.second);\n         \n        if(st.size()==1)\n        return cnt;\n        return 0 ;\n    }\n};\n\n\n\nclass Solution {\n    private:\n    int ans=0;\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        vector<int>consider(edges.size(),1);\n         fun(nums,edges,0,consider);\n         return ans;\n    }\n    void fun(vector<int>&nums, vector<vector<int>>&edges,int index,vector<int>&consider)\n    {\n        // cout<<"index:"<<index<<"    ans:"<<ans<<endl;\n        ans=max(makeComp(nums,edges,consider),ans);\n        //  cout<<endl;\n        if(index==edges.size())\n           return;\n\n        // let delete this\n         // pre-calculation\n         consider[index]=0;\n         fun(nums,edges,index+1,consider);\n         // post-calculation\n         consider[index]=1;\n        \n        // not delete this\n        fun(nums,edges,index+1,consider);\n         \n    }\n    int find(vector<int>&dsuf,int v)\n    {\n        if(dsuf[v]<0)\n         return v;\n        return dsuf[v]=find(dsuf,dsuf[v]);\n    }\n    void Union(vector<int>&dsuf,int from ,int to)\n    {\n        from=find(dsuf,from);\n        to=find(dsuf,to);\n        if(from!=to)\n        {\n            if(dsuf[from]<dsuf[to])\n            {\n                dsuf[from]+=dsuf[to];\n                dsuf[to]=from;\n            }\n            else\n            {\n                dsuf[to]+=dsuf[from];\n                dsuf[from]=to;\n            }\n        }\n    }\n  int makeComp(vector<int>&nums, vector<vector<int>>&edges,vector<int>&consider)\n    {  vector<int>dsuf(nums.size(),-1);\n    int cnt=0;\n        for(int i=0;i<consider.size();i++)\n         {\n             if(consider[i])\n            {\n                Union(dsuf,edges[i][0],edges[i][1]);\n            }\n            else\n              cnt++;\n         }\n        //  for(int i=0;i<dsuf.size();i++)\n        //   cout<<"node:"<<i<<"   parent:"<<dsuf[i]<<endl;\n\n         unordered_map<int,int>mp;\n         for(int i=0;i<dsuf.size();i++)\n         {\n             if(dsuf[i]<0)\n             {\n                mp[i]+=nums[i];\n             }\n             else\n             mp[dsuf[i]]+=nums[i];\n         }\n        unordered_set<int>st;\n        for(auto p:mp)\n        \n             st.insert(p.second);\n         \n        if(st.size()==1)\n        return cnt;\n        return 0 ;\n    }\n};\n```\n![upvote.jpeg](https://assets.leetcode.com/users/images/b74f5a20-f513-4a1b-9a40-61df7bb1f245_1675849980.0767183.jpeg)\n
['Tree', 'Depth-First Search', 'Graph', 'C++']