Faster solution O(MloglogM) where M is the sum of nodes
Prerequisite\nChoose an arbitrary root to make the tree rooted. 0 is the root thereafter.\nThe sum of nodes in the subtree (subtree-sum thereafter) rooted at ea
## Prerequisite\nChoose an arbitrary root to make the tree rooted. 0 is the root thereafter.\nThe sum of nodes in the subtree (subtree-sum thereafter) rooted at each node can be found by a simple DFS in O(N).\nLet M be the sum of all nodes, or in other words, the subtree-sum of the root.\n\n## Lemma\nThis solution is based on the following not so intuitive lemma:\n> For any divisor D of M, the tree can be divided into connected components (CCs) with the same sum D, if and only if D divides exactly M/D nodes\' subtree-sum.\n## Proof\n### "=>" direction\nFor any CC, consider its unique node closest to the root. The subtree rooted at this node is disconnected from the rest of the tree, so this subtree must consist of one or more CCs in their entirety. Therefore this node\'s subtree-sum is the sum of one more CCs and is divisible by D.\nConversely, if a node is not a CC\'s closest node to the root, let sub-CC be the intersection of this CC and the subtree rooted at this node. Note that sub-CC is a proper subset of CC, since this node\'s parent must also belong to this CC. Also, since nodes are all positive, sub-CC\'s sum is positive and strictly smaller than that of CC. The subtree-sum of this node is the sum of sub-CC and zero or more other CCs in their entirety, so if the subtree-sum divisible by D, the sub-CC\'s sum must be at least D, and the CC\'s sum is strictly larger than D, a contradiction.\nWe have shown that a node\'s subtree-sum is divisible by D if and only if it\'s a CC\'s unique closest node to the root. Since there are exactly M/D CCs, there are exactly M/D nodes whose subtree-sum is divisible by D.\n### "<=" direction:\nRemove all edges between non-root nodes whose subtree-sum is divisible by D and their parents. This splits the tree into M/D CCs. Each CC\'s sum must be positive and divisible by D, and thus at least D. Also, none of the CC\'s sum could larger than D since otherwise their sum will be larger than M, a contradition. Therefore all CC\'s sums are exactly D, and we found a valid solution.\n## Algorithm\nUse an array or a hashmap to count the number of subtree-sums equal to x for every integer x from 1 to M (inclusive). Let\'s call it `count`.\nEnumerate all divisors of D of M, starting from the smallest. The number of subtree-sums divisible by D is given by `count[D]+count[D*2]+...+count[M]`. If it is exactly M/D, return M/D-1.\nFor each D, it takes M/D steps to compute the summation. Therefore the complexity is the sum of M/D over all D\'s, which is the same as the sum of all D\'s. This is at most O(MloglogM). See https://en.wikipedia.org/wiki/Divisor_function#Growth_rate\n## Code\n### C++\n```\nclass Solution {\n    void dfs(int u,vector<int> &subsum,const vector<vector<int>> &adj,vector<bool> &vis){\n        vis[u]=true;\n        for(int v:adj[u])\n            if(!vis[v]){\n                dfs(v,subsum,adj,vis);\n                subsum[u]+=subsum[v];\n            }\n    }\npublic:\n    int componentValue(vector<int>& nums, vector<vector<int>>& edges) {\n        int n=nums.size();\n        vector<vector<int>> adj(n);\n        for(auto &e:edges){\n            adj[e[0]].push_back(e[1]);\n            adj[e[1]].push_back(e[0]);\n        }\n        vector<bool> vis(n);\n        dfs(0,nums,adj,vis);\n        int tot=nums[0];\n        vector<int> cnt(tot+1);\n        for(int x:nums)\n            cnt[x]++;\n        for(int d=1;d<tot;d++)\n            if(tot%d==0){\n                int c=0;\n                for(int i=d;i<tot;i+=d)\n                    c+=cnt[i];\n                if((c+1)*d==tot)\n                    return c;\n            }\n        return 0;\n    }\n};\n```\n### Python\n```\nclass Solution:\n    def dfs(self, u):\n        self.vis[u]=True\n        for v in self.adj[u]:\n            if not self.vis[v]:\n                self.dfs(v)\n                self.subsum[u]+=self.subsum[v]\n    def componentValue(self, nums: List[int], edges: List[List[int]]) -> int:\n        n=len(nums)\n        self.adj=[list() for _ in range(n)]\n        for u,v in edges:\n            self.adj[u].append(v)\n            self.adj[v].append(u)\n        self.vis=[False]*n\n        self.subsum=nums\n        self.dfs(0)\n        cnt=[0]*(max(self.subsum)+1)\n        for s in self.subsum:\n            cnt[s]+=1\n        tot=self.subsum[0]\n        for d in range(1,tot):\n            if tot%d==0:\n                c=0\n                for i in range(d,tot,d):\n                    c+=cnt[i]\n                if (c+1)*d==tot:\n                    return c\n        return 0\n```
['Depth-First Search', 'C', 'Python']