|
| 1 | +/** |
| 2 | + * 2440. Create Components With Same Value |
| 3 | + * https://leetcode.com/problems/create-components-with-same-value/ |
| 4 | + * Difficulty: Hard |
| 5 | + * |
| 6 | + * There is an undirected tree with n nodes labeled from 0 to n - 1. |
| 7 | + * |
| 8 | + * You are given a 0-indexed integer array nums of length n where nums[i] represents the value |
| 9 | + * of the ith node. You are also given a 2D integer array edges of length n - 1 where |
| 10 | + * edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. |
| 11 | + * |
| 12 | + * You are allowed to delete some edges, splitting the tree into multiple connected components. |
| 13 | + * Let the value of a component be the sum of all nums[i] for which node i is in the component. |
| 14 | + * |
| 15 | + * Return the maximum number of edges you can delete, such that every connected component in |
| 16 | + * the tree has the same value. |
| 17 | + */ |
| 18 | + |
| 19 | +/** |
| 20 | + *@param {number[]} nums |
| 21 | + *@param {number[][]} edges |
| 22 | + *@return {number} |
| 23 | + */ |
| 24 | +varcomponentValue=function(nums,edges){ |
| 25 | +constn=nums.length; |
| 26 | +constgraph=Array.from({length:n},()=>[]); |
| 27 | +consttotalSum=nums.reduce((sum,val)=>sum+val,0); |
| 28 | + |
| 29 | +for(const[u,v]ofedges){ |
| 30 | +graph[u].push(v); |
| 31 | +graph[v].push(u); |
| 32 | +} |
| 33 | + |
| 34 | +for(leti=n;i>=1;i--){ |
| 35 | +if(totalSum%i===0){ |
| 36 | +consttarget=totalSum/i; |
| 37 | +const[,components]=countNodes(0,-1,target); |
| 38 | +if(components===i){ |
| 39 | +returni-1; |
| 40 | +} |
| 41 | +} |
| 42 | +} |
| 43 | + |
| 44 | +return0; |
| 45 | + |
| 46 | +functioncountNodes(node,parent,target){ |
| 47 | +letsum=nums[node]; |
| 48 | +letcomponents=0; |
| 49 | + |
| 50 | +for(constneighborofgraph[node]){ |
| 51 | +if(neighbor!==parent){ |
| 52 | +const[childSum,childComponents]=countNodes(neighbor,node,target); |
| 53 | +sum+=childSum; |
| 54 | +components+=childComponents; |
| 55 | +} |
| 56 | +} |
| 57 | + |
| 58 | +if(sum===target){ |
| 59 | +return[0,components+1]; |
| 60 | +} |
| 61 | + |
| 62 | +return[sum,components]; |
| 63 | +} |
| 64 | +}; |