[CPP-Time-100%] Concise Solution with Topological  Sort and Bottom-Up Traversal
Intuition\n Describe your first thoughts on how to solve this problem. \nWe already have many posts using DFS or BFS. Here is an approach using toplogical sort.
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe already have many posts using DFS or BFS. Here is an approach using toplogical sort. According to the result, this approach beats 99.9+% w.r.t. time and 95+% w.r.t. space. As a result, we decide to share this post.\n\nGiven a target sum, we need to check whether it is possible to partition the tree so that each connected component meets such target. Our idea is quite simple: we always choose the node with least options (i.e. leaf). Either keep going or give up.\n\n1. If the value of current node "*Less Than*" the target, donate its value to its parent, remove the node from tree.\n2. If the value of current node "*Equals*" the target, remove the subtree of current node, add 1 to the counter.\n3. If the value of current node "*Greater Than*" the target, FAIL.\n4. Repeat Step 1~3 on next leaf.\n\nAs you all known, topological sort can give us such an order and meanwhile we can determine the parent of each node (except for the root) accordingly.\n\n# Complexity\n- Time complexity: O(N^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThis is the worst case estimation. The first N is calculated based on the possible numbers of components (we have at most n components). The second N is the number of nodes. Generally, the real performance is much better than this estimation.\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Code\n```\nint n;\nint top [20000];\nint cnt [20000];\nint par [20000];\nclass Solution {\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        ios::sync_with_stdio(false);\n        cin.tie(nullptr);\n        n=nums.size();\n        if(n==1)\n            return 0;\n        int m=0, ans=0, tar=0, sum=0;\n        vector<vector<int>> edge (n); \n        for(int i=0; i<n; ++i) {\n            cnt[i]=0;\n            par[i]=-1;\n            sum+=nums[i];\n            tar=max(tar, nums[i]);\n        }\n        //topo sort + parent of tree\n        for(int i=0; i<n-1; ++i) {\n            ++cnt[edges[i][0]];\n            ++cnt[edges[i][1]];\n            edge[edges[i][0]].push_back(edges[i][1]);\n            edge[edges[i][1]].push_back(edges[i][0]);\n        }\n        for(int i=0; i<n; ++i) {\n            if(cnt[i]==1) {\n                top[m++]=i;\n            }\n        }\n        for(int i=0; i<n; ++i) {\n            for(int p : edge[top[i]]) {\n                if(par[p]<0) {\n                    par[top[i]]=p;\n                }\n                if(--cnt[p]==1) {\n                    top[m++]=p;\n                }\n            }\n        }\n        //check\n        for(int i, j, k, m=sum/tar; m && !ans; --m) {\n            if(sum%m==0) {\n                tar=sum/m;\n                for(i=0; i<n; ++i) {\n                    cnt[i]=nums[i];\n                }\n                for(i=0, k=-1; i<n; ++i) {\n                    j=top[i];\n                    if(cnt[j]>tar) {\n                        // cout<<j<<":FAIL";\n                        k=-1;\n                        break;\n                    } else if(cnt[j]==tar) {\n                        // cout<<j<<":REM |";\n                        ++k;\n                    } else {\n                        cnt[par[j]]+=cnt[j];\n                        // cout<<j<<",";\n                    }\n                }\n                // cout<<"~"<<k<<"\\n";\n                ans=max(ans, k);\n            }\n        }\n        return ans;\n    }\n};\n```
['Greedy', 'Topological Sort']