创建价值相同的连通块

/*
 * 思路：
 * 1. 计算树中所有节点值的总和。
 * 2. 找到总和的所有可能的除数（这些除数是可能的连通块价值）。
 * 3. 使用DFS来验证树是否能分成这些连通块，使每个块的价值相等。
 * 4. 尝试所有可能的块价值，找出最大可以删除的边数。
 */

import java.util.*;
import java.util.stream.*;

public class EqualTreePartitionStream {
    public int maxNumEdgesToRemove(int[] nums, int[][] edges) {
        int totalSum = Arrays.stream(nums).sum();
        List<Integer> divisors = IntStream.rangeClosed(1, (int) Math.sqrt(totalSum))
                                           .filter(i -> totalSum % i == 0)
                                           .boxed()
                                           .flatMap(i -> Stream.of(i, totalSum / i))
                                           .distinct()
                                           .collect(Collectors.toList());
        Map<Integer, List<Integer>> graph = Arrays.stream(edges)
                                                   .flatMap(edge -> Stream.of(new AbstractMap.SimpleEntry<>(edge[0], edge[1]),
                                                                             new AbstractMap.SimpleEntry<>(edge[1], edge[0])))
                                                   .collect(Collectors.groupingBy(Map.Entry::getKey,
                                                                                  Collectors.mapping(Map.Entry::getValue, Collectors.toList())));
        int maxEdges = 0;

        for (int divisor : divisors) {
            if (divisor == 0 || divisor == totalSum) continue;
            Set<Integer> visited = new HashSet<>();
            if (canPartition(graph, nums, 0, visited, divisor) == totalSum / divisor) {
                maxEdges = Math.max(maxEdges, visited.size() - 1);
            }
        }
        return maxEdges;
    }

    private int canPartition(Map<Integer, List<Integer>> graph, int[] nums, int node, Set<Integer> visited, int target) {
        visited.add(node);
        int currentSum = nums[node];
        for (int neighbor : graph.get(node)) {
            if (!visited.contains(neighbor)) {
                currentSum += canPartition(graph, nums, neighbor, visited, target);
            }
        }
        if (currentSum == target) {
            return 0;
        }
        return currentSum;
    }

    public static void main(String[] args) {
        EqualTreePartitionStream etps = new EqualTreePartitionStream();
        int[] nums = {6, 2, 2, 2, 6};
        int[][] edges = {{0, 1}, {1, 2}, {1, 3}, {3, 4}};
        System.out.println(etps.maxNumEdgesToRemove(nums, edges));  // 输出：2
    }
}