[并查集][排序] Jzoj P2940 生成输入数据

Description

首先看到题目别太开心，这题可不是让你出数据～^_*

背景神马的就忽略了。这题就是给你一棵带边权的树，然后这棵树是某个完全图唯一的最小生成树。问原来的完全图中所有边可能的最小边权和是多少。

完全图是任意两个点之间都有边相连的图。

Input

第一行包含一个整数T表示数据组数。

每组数据第一行一个整数N表示点数。

接下来N-1行每行三个整数ai，bi，wi表示最小生成树上ai和bi之间有一条权值为wi的边。

Output

输出应有T行，每行表示一组数据的答案。

Sample Input

Sample Output

19
12

Data Constraint

Hint

20%的数据满足：T≤5，n≤5，wi≤5

另外30%的数据满足：n≤1000，给定的树是一条链

100%的数据满足：T≤10，n≤20000，wi≤10000

题解

题目大意：给定一棵最小生成树，问它的完全图的最小边权和为多少
我们可以先把每条边的权值从小到大排序
然后把n个点拆出来，再把n个点打入到最小生成树中
那么对于新加的一条边，它对答案的贡献显然就是(size[u]+size[v]-1)*(dis[u][v]+1)
因为完全图中两两点要有一条边相连，而且又不能改变给定的最小生成树，那么两点子树点两两相连，距离就是两点距离+1

代码

 1 #include <cstdio>
 2 #include <algorithm>
 3 #define N 20020
 4 #define ll long long
 5 using namespace std;
 6 struct edge { ll x,y,v; }e[N];
 7 ll T,n,fa[N],size[N],ans;
 8 bool cmp(edge a,edge b) {  return a.v<b.v; }
 9 ll getfather(ll x) { return (fa[x]==x)?x:fa[x]=getfather(fa[x]); }
10 int main()
11 {
12     scanf("%lld",&T);
13     while (T--)
14     {
15         scanf("%lld",&n);
16         for (ll i=1;i<n;i++) scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].v);
17         for (ll i=1;i<=n;i++) fa[i]=i,size[i]=1;
18         sort(e+1,e+n,cmp),ans=0;
19         for (ll i=1;i<n;i++)
20         {
21             ll u=getfather(e[i].x),v=getfather(e[i].y);
22             if (u!=v) ans+=(size[u]*size[v]-1)*(e[i].v+1),size[u]+=size[v],fa[v]=u,ans+=e[i].v;
23         }
24         printf("%lld
",ans);
25     }
26 }