题目描述
思路解析
一句话答案：LeetCode 2285 道路的最大总重要性：一座城市的贡献是它的值乘度数，所以把大值配给度数大的城市——数度数、升序排、第 i 位配值 i，累加即最优，时间 O(m + n log n)。
给城市配 1 到 n 的值，让所有路的重要性之和最大
有 n 座城市，编号 0 到 n−1，还有若干条双向道路。你要给每座城市分一个 1 到 n 的整数，每个值只用一次。一条路的重要性是它连的两座城市值相加；所有路的重要性加起来，最大能到多少。题面例子 n=5、六条路 roads=[[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]，最优分配下答案是 43。
值有 n 的阶乘种排法，一种种试根本试不完
1 到 n 分给 n 座城市，排法有 n 的阶乘种，n 到五万量级根本没法枚举；何况每换一种分配都要把每条路重加一遍。这条路走不通。可总和是每座城市的值被反复加出来的。
一座城市的值，被它每条路各加进总和一次
别盯着路，盯着城市。某座城市分到的值，会被它连的每一条路各拿去加一次。它连了几条路，这个数叫它的度数，那它的值就在总和里出现几次。于是一座城市的贡献，就是它的值乘度数；整个答案就是所有城市「值 × 度数」之和。
剩下就是把 1 到 n 分下去、让这个乘积和最大。答案是大值配大度数：度数大的城市，值被加进总和更多次，理应拿最大值。这就是排序不等式——两组数两两相乘再求和，大的配大的、小的配小的，总和才最大，配反了只会变小。
数度数、升序排、第 i 位配上值 i
落到代码就三步。先开一个长度 n 的数组记度数，扫一遍路，每条路给它的两个端点各加 1。再把这排度数从小到大排好，最右就是最大度数。最后从左往右走，第 1 个位置配值 1、第 2 个配值 2，直到第 n 个配值 n，把每个「度数 × 该值」累加就是答案。
这步不必真记哪座城市分到几——排好序的度数逐位乘上 1 到 n 求和，就已经等价于大值配大度数。
n=5 那六条路，43 是怎么一位位加出来的
先数度数：六条路各给两端加 1，数完按城市编号排是 [2,3,4,2,1]——城 2 连四条最多，城 1 连三条，城 0 和城 3 各两条，城 4 只一条。
把这排度数升序排好，变成 [1,2,2,3,4]。从左往右配值：第 1 位度数 1 配值 1，1 × 1 = 1；第 2 位度数 2 配值 2，2 × 2 = 4；第 3 位度数 2 配值 3，3 × 2 = 6；第 4 位度数 3 配值 4，4 × 3 = 12；第 5 位度数 4 配值 5，5 × 4 = 20。五份贡献 1 + 4 + 6 + 12 + 20 加起来是 43。
复杂度只有排序那一项，坑全在整型和边界上
数度数扫一遍路是 O(m)，m 是路的条数；排序 n 个度数是 O(n log n)；累加是 O(n)。主导项是排序，整体 O(m + n log n)，空间 O(n)，就是度数数组。
真正容易出事的不是算法，是溢出：n 和度数都能到五万量级，值乘度数再累加会顶破 32 位整数，C++ 和 Java 得用 long long 或 long 存和、乘法先转长整型，Python 的整数没有上限不受影响。几个小边界顺带核一遍：两座城一条路，度数 [1,1] 配值 1、2 得 3；三座城连成三角，度数全是 2、配值 1 到 3 得 2 + 4 + 6 = 12；例二答案 20 同样能验出来。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这条主线:一座城市的贡献是它的值乘以它的度数。想让总贡献最大,就让度数大的城市拿大值。所以先数度数,再从小到大排,让排在越后面度数越大的城市,拿到越大的值。下面先在图上把度数数出来。
初始 · 5 座城市,度数全为 0：舞台上是 5 座城市,编号 0 到 4,城市之间的连线就是双向道路。第一步和值多大没关系,先把每座城市的度数数出来,也就是它连了几条路。开始时每座城市旁边的度数都标着 0,接下来一条一条路地扫,给这条路的两个端点各加 1。
第 1 / 6 条路 · [0, 1]：看第 1 条路 [0, 1]。高亮的就是眼下这条路,它连着城 0 和城 1。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [0, 1] 数完 · 城 0 度数到 1,城 1 度数到 1：两头各加 1:城 0 的度数变成 1,城 1 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 2 / 6 条路 · [1, 2]：看第 2 条路 [1, 2]。高亮的就是眼下这条路,它连着城 1 和城 2。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [1, 2] 数完 · 城 1 度数到 2,城 2 度数到 1：两头各加 1:城 1 的度数变成 2,城 2 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 3 / 6 条路 · [2, 3]：看第 3 条路 [2, 3]。高亮的就是眼下这条路,它连着城 2 和城 3。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [2, 3] 数完 · 城 2 度数到 2,城 3 度数到 1：两头各加 1:城 2 的度数变成 2,城 3 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 4 / 6 条路 · [0, 2]：看第 4 条路 [0, 2]。高亮的就是眼下这条路,它连着城 0 和城 2。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [0, 2] 数完 · 城 0 度数到 2,城 2 度数到 3：两头各加 1:城 0 的度数变成 2,城 2 的度数变成 3。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 5 / 6 条路 · [1, 3]：看第 5 条路 [1, 3]。高亮的就是眼下这条路,它连着城 1 和城 3。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [1, 3] 数完 · 城 1 度数到 3,城 3 度数到 2：两头各加 1:城 1 的度数变成 3,城 3 的度数变成 2。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
第 6 / 6 条路 · [2, 4]：看第 6 条路 [2, 4]。高亮的就是眼下这条路,它连着城 2 和城 4。数度数很机械,一条路给它的两个端点各记一笔,先不管这两座城市将来分到多大的值。
路 [2, 4] 数完 · 城 2 度数到 4,城 4 度数到 1：两头各加 1:城 2 的度数变成 4,城 4 的度数变成 1。度数谁高谁低先别急着下结论,扫到一半的中间态容易看走眼,等 6 条路全数完再一起比,才知道谁是最忙的枢纽。
度数数完 · deg = [2, 3, 4, 2, 1]：6 条路全数完了。按城市编号排,度数是 [2, 3, 4, 2, 1]:城 2 连了 4 条路最多,城 1 连 3 条,城 0 和城 3 各连 2 条,城 4 只连 1 条最少。度数一出来,谁该拿大值就清楚了:城 2 该拿最大的 5,城 4 拿最小的 1。下面把这些度数排个序,让分配一目了然。
度数按城市编号排成一排：把刚才每座城市的度数抄成一排,从左到右是城 0 到城 4,值分别是 2、3、4、2、1。现在它是乱的,不方便配值。下一步把它从小到大排好,这样越靠右度数越大,正好对应越大的值。
升序排好 · [1, 2, 2, 3, 4]：排好序,现在是 [1, 2, 2, 3, 4]。最左边是最小的度数 1,最右边是最大的度数 4。接下来从左往右走,第 1 个位置配值 1,第 2 个配值 2,一直到第 5 个配值 5。位置越靠右度数越大,拿到的值也越大,这就把大值稳稳配给了大度数。
第 1 位 · 度数 1 配值 1：走到第 1 个位置,这里度数是 1,按规矩配上值 1。这座城市的贡献就是值乘度数,1 × 1 = 1。把它加进累计和,累计从 0 变成 1。继续往右,度数更大的位置会配更大的值。
第 2 位 · 度数 2 配值 2：走到第 2 个位置,这里度数是 2,按规矩配上值 2。这座城市的贡献就是值乘度数,2 × 2 = 4。把它加进累计和,累计从 1 变成 5。继续往右,度数更大的位置会配更大的值。
第 3 位 · 度数 2 配值 3：走到第 3 个位置,这里度数是 2,按规矩配上值 3。这座城市的贡献就是值乘度数,3 × 2 = 6。把它加进累计和,累计从 5 变成 11。继续往右,度数更大的位置会配更大的值。
第 4 位 · 度数 3 配值 4：走到第 4 个位置,这里度数是 3,按规矩配上值 4。这座城市的贡献就是值乘度数,4 × 3 = 12。把它加进累计和,累计从 11 变成 23。继续往右,度数更大的位置会配更大的值。
第 5 位 · 度数 4 配值 5：走到第 5 个位置,这里度数是 4,按规矩配上值 5。这座城市的贡献就是值乘度数,5 × 4 = 20。把它加进累计和,累计从 23 变成 43。这是最大的度数配上了最大的值,贡献也最大。
全部配完 · 答案 = 43：五个位置全配完了。把每位的贡献 1 + 4 + 6 + 12 + 20 加起来,正好是 43。这就是最优分配下所有道路重要性之和的最大值。回头看,大值都落在了度数大的城市上,一分值也没浪费在冷清的城市上,这就是排序不等式给的最优安排。
边界想清:两城一路记 3、示例二核到 20、三城全连时度数相同配值 1 到 3 得 12。
面试重点:贡献拆成值×度数、排序不等式保证大值配大度数最优、O(m + n log n) 且注意长整型防溢出。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def maximumImportance(self, n: int, roads: List[List[int]]) -> int: deg = [0] * n for a, b in roads: deg[a] += 1 deg[b] += 1 deg.sort() return sum(i * v for i, v in enumerate(deg, 1))复杂度
- 时间：O(m + n log n)，m 是路的条数,数度数扫一遍 roads 是 O(m);再对 n 个度数排序是 O(n log n);最后遍历累加是 O(n)。主导项是排序的 O(n log n),整体就是 O(m + n log n)
- 空间：O(n)，按峰值算,主要是那个长度为 n 的度数数组,O(n)。排序本身的额外开销:C plus plus 和 Java 通常是 O(log n) 递归栈,Python 的排序最坏 O(n),都不超过度数数组的量级,所以整体空间 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心洞察是什么?
追问为什么大值配大度数就是最优,能证明吗?
追问复杂度是多少,有什么实现坑?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
网格中的最小路径代价
LeetCode 2304 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题