C++ solution, faster than 40% submissions
Question : Find the max number of edges that you can delete, such that all sub-components have the same sum.\n\nIdea : \nFirst, calculate the sum of all nodes a
Question : Find the max number of edges that you can delete, such that all sub-components have the same sum.\n\nIdea : \nFirst, calculate the sum of all nodes as S. To split them into n components, S % n must be 0 (primary school maths).\n\nThen, you can inspect the tree. Each node must belongs to any sub-component.\n\nThe value of all sub-component is (S / n).\n\nSo, if the current node\'s value is already (S / n), it is a sub-component itself. So, remove all the edges between this and the child / children, and if any child\'s sum != (S / n), it is invalid. Why? Because the current node can\'t take in more values.\n\nIf the current node\'s value is < (S / n), then check the children. For all the children with sub-sum < (S / n), group them together. Since it is a tree, those children can only connect to this parent node.\n\nRecall that all nodes must belongs to any sub-component. Therefore, those children with sub-sum < (S / n) can only be grouped with the current parent.\n\n*Imagine that if you left out any child (-_-) with sub-sum < S / n, that child cannot be connected to any other nodes (T_T) (poor child). Since that child cannot be a sub-component, it is invalid.*\n\nSo, that\'s the entire idea (-_-;)\n\n```cpp\nclass Solution {\npublic:\n    int maxn;\n    int sumn;\n    int pat_val, pat_size;\n    const static int MAX = 20010;\n    bool mk[MAX];\n    int edges_del;\n    int max_edges_del;\n    bool flag;\n    std::map<int, vector<int>> T;\n    void T_init_insert(int a, int b) {\n        if (T.find(a) == T.end()) {\n            T[a] = { b };\n        }\n        else {\n            T[a].push_back(b);\n        }\n    }\n    int T_ck(vector<int>& nums, int cur_n) {\n        if (!flag)\n            return -1;\n        if (nums[cur_n] > pat_val) {\n            flag = false;\n            return -1;\n        }\n        mk[cur_n] = true;\n        int cvaltmp, rescval;\n        if (nums[cur_n] == pat_val) {\n            for (int des : T[cur_n]) {\n                if (!mk[des]) {\n                    edges_del++;\n                    int cval = T_ck(nums, des);\n                    if (!flag)\n                        return -1;\n                    if (cval != pat_val) {\n                        flag = false;\n                        return -1;\n                    }\n                }\n            }\n            return pat_val;\n        }\n        else {\n            cvaltmp = 0;\n            for (int des : T[cur_n]) {\n                if (!mk[des]) {\n                    int cval = T_ck(nums, des);\n                    if (cval > pat_val) {\n                        flag = false;\n                        return -1;\n                    }\n                    else if (cval == pat_val) {\n                        edges_del++;\n                    }\n                    else {\n                        cvaltmp += cval;\n                    }\n                }\n            }\n            rescval = nums[cur_n] + cvaltmp;\n            if (rescval > pat_val) {\n                flag = false;\n                return -1;\n            }\n            return rescval;\n        }\n        return -1;\n    }\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        max_edges_del = 0;\n        maxn = -1;\n        sumn = 0;\n        for (int v : nums) {\n            sumn += v;\n            maxn = std::max(maxn, v);\n        }\n        for (vector<int> e : edges) {\n            T_init_insert(e[0], e[1]);\n            T_init_insert(e[1], e[0]);\n        }\n        int bound = (int)std::ceil(std::sqrt((sumn * 1.0)));\n        for (int d = 1; d < bound; d++) {\n            if ((sumn % d) == 0) {\n                flag = true;\n                edges_del = 0;\n                memset(mk, false, sizeof(mk));\n                pat_val = d;\n                pat_size = sumn / d;\n                T_ck(nums, 0);\n                \n                if (flag) {\n                    max_edges_del = std::max(max_edges_del, edges_del);\n                }\n                flag = true;\n                edges_del = 0;\n                memset(mk, false, sizeof(mk));\n                pat_val = sumn / d;\n                pat_size = d;  \n                T_ck(nums, 0);\n                if (flag) {\n                    max_edges_del = std::max(max_edges_del, edges_del);\n                }\n            }\n        }\n        return max_edges_del;\n    }\n};\n\n```
[]