题目链接：1147. 构造完全图 - AcWing题库
分析：解题思路：
完全图的定义：每对不同的点之间恰有一条边相连
先按照正常求最小生成树的方法，按边权排序边
由于题目给我们的边恰好就是一颗最小生成树，说明一条边连接的两个点必然属于两个不同的集合。
答案应该+当前枚举的边权+（当前枚举的集合A中点的数量*当前枚举的集合B中点的数量-1）*（当前枚举的边权+1）注：-1 是因为有一条边就是当前枚举的这条边。 +1 是因为要使新的完全图的最小生成树不会被改变。
修改完当前答案之后，合并两个联通块，在合并两个集合，即如果联通块A往联通块B去合并，那么集合B的点的数量+=集合A中点的数量。
上代码～！
N = int(input())
group = [i for i in range(N+1)]
nums = [1 for i in range(N+1)] # 开始每个集合都只有自己1个点
edges = []
res = 0
for i in range(N-1) :
a,b,c = map(int,input().split())
edges.append((a,b,c))
edges.sort(key = lambda x : x[2])
def root(x) :
if x != group[x] :
group[x] = root(group[x])
return group[x]
def union(x,y) :
group[root(x)] = root(y)
for i in range(N-1) :
a,b,c = edges[i]
a,b = root(a),root(b)
res += c
res += (nums[a]*nums[b]-1)*(c+1)
union(a,b)
nums[b] += nums[a] #认谁当祖宗就往谁的集合合并
print(res)
