1. 解题思路
这一题主要是在问题的分析上面。由题意易知，事实上给定的图必然只可能存在三种可能的结构：
- 孤立的点
- 链状结构
- 环状结构
其中，孤立的点必然不会有贡献，可以直接忽略，我们只需要考察环状结构和链状结构。
其中，对于环状结构，其长度事实上没有影响，任何一个元素无论放在何等长度的环上面其贡献都是一致的，因为它只与其相邻元素相关。而要想要其贡献最大化，其最合适的结构必然是以最大元素为中心，然后分别向左右逐一辐射。
而对于链状结构，其构造方式和环状结构差不多，但是其首尾不相连，因此必然浪费了一次乘积结果，因此，我们应该使得两侧的元素越小越好。
综上，最佳的构造方式就是：
- 优先将大元素分配给环；
- 对于链状结构，按长度从高到低依次进行元素分配。
此时，我们剩下的问题就是如何找环和链了。要找链，我们只需要找到度为1的节点即可，其必为链的一侧端点，然后进行遍历即可。而对于环，只需要在剩下的节点当中随意找一个节点作为起点即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def maxScore(self, n: int, edges: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
nodes = [u for u in range(n) if len(graph[u]) == 1] + [u for u in range(n) if len(graph[u]) == 2]
def get_max(m, k, is_circle):
if k == 1:
return 0
nums = [m-i for i in range(k)]
nums = nums[1::2][::-1] + nums[::2]
ans = sum([nums[i] * nums[i+1] for i in range(k-1)])
return ans if not is_circle else ans + nums[0] * nums[-1]
ans = 0
lines = []
status = [0 for _ in range(n)]
for i in nodes:
if status[i] == 1:
continue
u = i
length = 0
while status[u] == 0:
status[u] = 1
length += 1
for v in graph[u]:
if status[v] == 0:
u = v
break
if i in graph[u] and length > 2:
ans += get_max(n, length, True)
n -= length
else:
lines.append(length)
lines = sorted(lines, reverse=True)
for length in lines:
ans += get_max(n, length, False)
n -= length
return ans
提交代码评测得到：耗时325ms，占用内存44.2MB。