题目描述
对于完全图G ，若有且仅有一棵最小生成树T ，则称完全图 G 是树 T 扩展出的。
给你一棵树T ，找出 T 能扩展出的边权和最小的完全图 G。
输入格式
第一行正整数N 表示树 T 的点数；
接下来 N-1 行三个整数u,v,w ；描述一条边 （u,v） 权值为 w；
保证输入数据构成一棵树。
输出格式
输出仅一个数，表示最小的完全图 G 的边权和。
样例
样例输入
4
1 2 1
1 3 1
1 4 2
样例输出
12
数据范围与提示
对于20% 的数据，N<=10；
对于50% 的数据，m<=1000；
对于100% 的数据，N<=1E50，1<=W<=1E5。
分析：
一个图的最小生成树可能不止一个。本题图G有唯一的最小生成树T。下图T是G的唯一最小生成树：
我们把最小生成树T的BD边断开，原来的最小生成树分成了两部分(T1，T2)。
T1，T2中分别有3个节点，能将T1，T2连成生成树的边有9条（BD,BE,BF；AD,AE,AF；CD,CE,CF）。
BD是最小生成树中的边的唯一原因就是，BD比其它8条都短。
反过来将，其它8条边都比BD大，为了保证原图权值和最小，那就让其它8条边只比BD长度大1。
设BD长度为w ，那这9条边的总长度为w+(3*3-1)*(w+1)。
按边长从小到大的顺序检查最小生成树上的每一条边的长度w，同时累计当时没挑中的那些边的总长度。
一开始每个点所属的子树编号就是自己的编号，当挑中一条边时：
1）这条边两个端点合并到一个子树中
2）计算没挑选的那些边的数量，累计边长和。
3）更新子树中的节点个数
详细步骤：
{A}、{B}、{C}、{D}、{E}、{F}
1)选边AC ,合并AC {A,C}、{B}、{D}、{E}、{F}
sum+=WAC
2)选边DE ,合并DE {A,C}、{B}、{D,E}、{F}
sum+=WDE
3)选边AB ,合并AB {A,C,B}、{D,E}、{F}。
能合并AB两个子树的边还有BC,但是选了AB的原因是因为AB比BC小，为了保证完全图的权值和尽可能小，我们让BC之比AB大1。
sum+=WAB+WBC
sum+=WAB+WAB+1
4)选边DF ,合并DF {A,C,B}、{D,E,F}
能合并D，F两个子树的边还有EF,但是选了DF的原因是因为DF比EF小，为了保证完全图的权值和尽可能小，我们让EF之比DF大1。
sum+=WDE+WEF
sum+=WDE+WDE+1
4)选边BD ,合并BD {A,C,B,D,E,F}
能合并B,D两个子树的边还有(BE,BF；AD,AE,AF；CD,CE,CF)8条,但是选了BD的原因是因为它比其它8条边都小，为了保证完全图的权值和尽可能小，我们让其它8条边只比BD大1。
sum+=WBD+WBE+WBF+WAD+WAE+WAF+WCD+WCE+WCF
sum+=WBD+8*(WBD+1)
参考代码：
1 /*
2
3 4
4 1 2 1
5 1 3 1
6 1 4 2
7
8 12
9 */
10
11 #include <bits/stdc++.h>
12 using namespace std;
13
14 inline int read() {
15 int f = 1, x = 0;
16 char ch = getchar();
17 while (ch > '9' || ch < '0') {
18 if (ch == '-')
19 f = -1;
20 ch = getchar();
21 }
22 while (ch >= '0' && ch <= '9') {
23 x = (x << 1) + (x << 3) + (ch ^ 48);
24 ch = getchar();
25 }
26 return f * x;
27 }
28 const int MaxN = 1e5+5;
29
30
31 int n;
32 long long sum=0;
33
34 int fa[MaxN];
35 int cnt[MaxN];//cnt[i] 表示i点所在的子生成树中的节点个数
36
37 int Find(int x) {
38 if (fa[x])
39 return fa[x] = Find(fa[x]);
40 return x;
41 }
42
43 struct edge {
44 int u, v;
45 int w;
46 } edges[MaxN];//存n-1条边
47
48 bool cmp(edge e1,edge e2) //按边长升序
49 {
50 return e1.w < e2.w;
51 };
52
53 int main() {
54 n = read();
55
56 for (int i = 1; i <= n-1; i++)
57 {
58 edges[i].u = read(); edges[i].v = read(); edges[i].w = read();
59 sum+=edges[i].w;//求最小生成树中边权和
60 cnt[i]=1; //
61 }
62 cnt[n]=1;
63
64 sort(edges+1,edges+1+n-1,cmp);
65
66 for (int i = 1; i <= n-1; i++) //按边长从小到大的顺序处理
67 {
68 int u=edges[i].u,v=edges[i].v,w=edges[i].w;
69 int fau=Find(u),fav=Find(v);
70 sum+=1ll*(w+1)*(cnt[fau]*cnt[fav]-1);
71 fa[fau]=fav;
72 cnt[fav]=cnt[fav]+cnt[fau];
73 }
74 cout<<sum<<endl;
75
76
77
78
79 return 0;
80 }
标签：BD,ch,sum,最小,完全,生成,AB,构造 From： https://www.cnblogs.com/flatte/p/17620567.html