以下是 LeetCode 3547. 图中边值的最大和 的 Java 实现。

解题思路

由于每个节点最多与其他两个节点相连，整个图由若干链和环组成。核心贪心策略：

1. 先处理环，再处理链——环的每节点度数为 2，能贡献更多边权；链至少有一个端点度数为 1。
2. 链按长度降序处理——长链能贡献更多边，优先分配大数。
3. 填数策略——将剩余的最大数放在连通分量的中间，次大的数交替向两边扩展，使得大数尽量相邻（类似排序不等式）。

时间复杂度 O(n \log n)，空间复杂度 O(n)。

---

Java 代码

```java
import java.util.*;

class Solution {
    public long maxScore(int n, int[][] edges) {
        long ans = 0;
        
        // 建图
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph[u].add(v);
            graph[v].add(u);
        }
        
        boolean[] seen = new boolean[n];
        List<Integer> cycleSizes = new ArrayList<>();  // 所有节点度数为2的连通分量（环）
        List<Integer> pathSizes = new ArrayList<>();   // 其余连通分量（链）
        
        // 遍历每个连通分量
        for (int i = 0; i < n; i++) {
            if (seen[i]) continue;
            List<Integer> component = getComponent(graph, i, seen);
            // 判断是否为环：所有节点度数均为2
            boolean allDegree2 = true;
            for (int u : component) {
                if (graph[u].size() != 2) {
                    allDegree2 = false;
                    break;
                }
            }
            if (allDegree2) {
                cycleSizes.add(component.size());
            } else if (component.size() > 1) {
                pathSizes.add(component.size());
            }
            // 孤立点（size==1）不贡献边权，无需处理
        }
        
        // 先处理环：从剩余的最大数中分配
        for (int cycleSize : cycleSizes) {
            ans += calculateScore(n - cycleSize + 1, n, true);
            n -= cycleSize;
        }
        
        // 链按长度从大到小排序，优先处理长链
        Collections.sort(pathSizes, Collections.reverseOrder());
        for (int pathSize : pathSizes) {
            ans += calculateScore(n - pathSize + 1, n, false);
            n -= pathSize;
        }
        
        return ans;
    }
    
    // BFS/DFS 获取连通分量中的所有节点
    private List<Integer> getComponent(List<Integer>[] graph, int start, boolean[] seen) {
        List<Integer> component = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        seen[start] = true;
        component.add(start);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : graph[u]) {
                if (!seen[v]) {
                    seen[v] = true;
                    queue.offer(v);
                    component.add(v);
                }
            }
        }
        return component;
    }
    
    /**
     * 计算将 [left, right] 范围内的数填入一个连通分量的最大边权和
     * 
     * 填数策略：用双端队列模拟，初始放入两个最大值 right
     * 从 right-1 递减到 left，每次取出队列前端与当前值相乘，再将当前值放入队尾
     * 这样大数会集中在中间，次大数交替向两边扩展
     * 
     * @param left    可用数的最小值
     * @param right   可用数的最大值
     * @param isCycle 是否为环（环需要额外加上首尾相连的一条边）
     * @return 该连通分量的最大边权和
     */
    private long calculateScore(int left, int right, boolean isCycle) {
        Deque<Long> deque = new ArrayDeque<>();
        deque.offerLast((long) right);
        deque.offerLast((long) right);
        long score = 0;
        
        for (int value = right - 1; value >= left; value--) {
            long windowValue = deque.pollFirst();
            score += windowValue * value;
            deque.offerLast((long) value);
        }
        
        // 如果是环，首尾两个节点也相邻，额外加上它们的乘积
        if (isCycle) {
            score += deque.peekFirst() * deque.peekLast();
        }
        return score;
    }
}
```

---

关键说明

要点    说明    
连通分量分类    所有节点度数均为 2 → 环；否则为链（含孤立点）    
处理顺序    环优先于链，因为环的每个节点都有两条边，大数在环中能产生更多乘积；链按长度降序，长链优先拿大数    
calculateScore    双端队列模拟"中间放大数，向两边递减"的排列。例如 `[left..right]=[7,8,9,10,11]`，排列为 `9-11-10-8-7`，相邻乘积和最大    
环额外处理    环首尾相连，所以 `deque.peekFirst() * deque.peekLast()` 是最后一条边的贡献    

> 注意：这道题在赛后被社区发现部分测试数据存在争议（官方答案可能不是最优），但上述贪心策略是标准竞赛解法。