2025-10-30：图中边值的最大和。用go语言，给定一个包含 n 个顶点的无向连通图，顶点编号为 0 到 n−1，且每个顶点最多与两个其它顶点相连（度 ≤ 2）。图中共有 m 条边，用数组 edges 表示，其中 edges[i] = [ai, bi] 表明顶点 ai 与 bi 有一条边相连。

现在需要把 1 到 n 之间的整数分别、互不相同地分配给各顶点。每条边的值定义为其两个端点所分配数的乘积，整个图的得分为所有边值的和。求可以达到的最大总得分并返回该值。

1 <= n <= 5 * 10000。

m == edges.length。

1 <= m <= n。

edges[i].length == 2。

0 <= ai, bi < n。

ai != bi。

图中不存在重复边。

图是连通的。

每个节点最多与其他两个节点相连。

输入： n = 6, edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]。

输出： 82。

解释：

上图展示了一个最优的节点值分配方式。边值的总和为：(1 * 2) + (2 * 4) + (4 * 6) + (6 * 5) + (5 * 3) + (3 * 1) = 82。

题目来自力扣3547。

1. 问题理解与图结构分析

这个问题要求我们在一个特殊的无向连通图中分配数字以最大化边值总和：

• 图结构特性：由于每个顶点度数 ≤ 2 且图连通，该图只能是路径（链）或环
  • 当边数 m = n-1 时，图为路径
  • 当边数 m = n 时，图为环
• 目标函数：每条边的值是两个端点分配数值的乘积，需要最大化所有边值的总和

2. 最优分配策略推导

2.1 路径（链）情况分析

对于路径 v₁ — v₂ — v₃ — ... — vₙ，边值总和为：

S = v₁v₂ + v₂v₃ + v₃v₄ + ... + vₙ₋₁vₙ

关键观察：

• 中间节点（v₂ 到 vₙ₋₁）出现在两个乘积中
• 端点节点（v₁ 和 vₙ）只出现在一个乘积中

最优策略：

• 将最大的 n-2 个数（3, 4, …, n）分配给中间节点
• 将最小的两个数（1 和 2）分配给端点节点

2.2 环情况分析

在环中：

• 每个顶点都出现在两条边中
• 所有顶点的值都被使用两次

最优策略：

• 环的最优分配与路径相似
• 但需要额外考虑闭合边的影响
• 从推导可知，环的最优值比路径的最优值恰好大 2

3. 数学公式推导

3.1 路径情况公式

代码中使用的基础公式：

ans = (n²×2 + n×5 - 6) × (n-1) / 6

这个闭式公式是通过数学推导得到的路径情况最优解。

3.2 环情况调整

当检测到图是环时（n == len(edges)）：

ans += 2

这个 +2 的调整是因为在环结构中，通过最优排列可以使最小两个数（1 和 2）相乘，为总分贡献额外的 2。

4. 算法执行过程

1. 输入处理：接收顶点数 n 和边列表 edges
2. 图类型判断：通过比较 n 和 edges 长度判断是路径还是环
3. 基础计算：使用推导出的数学公式计算路径情况的最优值
4. 环调整：如果是环，在基础值上加 2
5. 结果返回：返回计算得到的最大边值总和

5. 示例验证

对于输入 n = 6, edges 有 6 条边：

• 基础计算：(6²×2 + 6×5 - 6) × (6-1) / 6 = 80
• 环调整：80 + 2 = 82
• 与题目给出的最优分配结果一致

6. 复杂度分析

时间复杂度：O(1)

• 只进行固定次数的算术运算
• 不随输入规模 n 增长而变化
• 无需遍历图结构或边列表

空间复杂度：O(1)

• 只使用固定数量的整型变量
• 不依赖输入规模的额外存储空间
• 算法原地计算，无需辅助数据结构

总结

该解法充分利用了图的特殊结构特性（度数限制导致只能是路径或环），通过数学推导得到了最优分配的闭式解，避免了复杂的图遍历和搜索过程，实现了极致的时间效率和空间效率。

Go完整代码如下：

package main

import (
	"fmt"
)

func maxScore(n int, edges [][]int) int64 {
	ans := (n*n*2 + n*5 - 6) * (n - 1) / 6
	if n == len(edges) { // 环
		ans += 2
	}
	return int64(ans)
}

func main() {
	n := 6
	edges := [][]int{{0, 3}, {4, 5}, {2, 0}, {1, 3}, {2, 4}, {1, 5}}
	result := maxScore(n, edges)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def max_score(n: int, edges: list[list[int]]) -> int:
    ans = (n * n * 2 + n * 5 - 6) * (n - 1) // 6
    if n == len(edges):  # 环
        ans += 2
    return ans

def main():
    n = 6
    edges = [[0, 3], [4, 5], [2, 0], [1, 3], [2, 4], [1, 5]]
    result = max_score(n, edges)
    print(result)

if __name__ == "__main__":
    main()