题目大意：

给一个图，每个边长度分别为1~m，让你选出n-1个边，造一个权重最小的树（显然为最小生成树，并且唯一）

并求出这棵树，任意2点之间连线的距离的期望。

官方题解：

首先注意到任意两条边的边权是不一样的，由此得知最小生成树是唯一的，最小生成树既然 是唯一的，那么期望其实也就是唯一的，不存在什么最小期望。求完最小生成树之后，接下 来的问题就可以转换成在最小生成树上求任意两点之间距离的平均值，对于每条边，统计所 有的路径用到此边的次数，也就是边的两端的点数之积。那么这条边的总贡献就是次数*边 权。最后得到所有边的贡献之和再除以总路径数$n\ast (n-1)/2$就是答案。可以$On$求出。任取一点为根dfs，对每个点$i$记录其子树包含的点数（包括其自身），设点数为$sum[i]$，则$i$的父亲一侧的点数即为$n-sum[i]$。一边遍历一边统计就行。

看了题解，总之很简单就对了。

然后有一个细节。。。WA了好久，MST得到边的时候，添加a->b，而不要不小心弄成添加 fa(A)  -> fa(B)!!!!!!

切记切记！ 这题会炸INT~

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;


#define LL long long
LL n, m;
const int maxm = 1000010;
const int maxn = 100010;


struct edge
{
	LL u, v, w;
}e[maxm];

struct CMP
{
	bool operator () (edge arg0, edge arg1)
	{
		return arg0.w < arg1.w;
	}
};


struct node
{
	LL t, w;
	node(LL a, LL b)
	{
		t = a;
		w = b;
	}
};

vector<node>g[maxn];

LL fa[maxn];

LL getfa(LL k)
{
	if (fa[k]==0)	return k;
	fa[k] = getfa(fa[k]);
	return fa[k];
}

void init()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i != maxn; ++ i)	g[i].clear();
	for (int i = 0; i != m; ++ i)
	{
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
	}
	sort(e, e + m, CMP());
	memset(fa, 0, sizeof(fa));
	LL ans1=0;
	for (int i = 0; i != m; ++ i)
	{
		LL u = e[i].u;
		LL v = e[i].v;
		LL w = e[i].w;
		u = getfa(u);
		v = getfa(v);
		if (u == v)	continue;
		ans1 += (LL)w;
		fa[u] = v;
		g[e[i].u].push_back(node(e[i].v, w));
		g[e[i].v].push_back(node(e[i].u, w));
	}
	printf("%lld ", ans1);
}

LL son[maxn];
LL ans;

LL dfs(LL k, LL fa)
{
	son[k] = 1;
	for (int i = 0; i != g[k].size(); ++i)
	{
		LL will = g[k][i].t;
		if (will == fa)	continue;
		son[k] += dfs(will, k);
		ans += (n-son[will] ) * son[will] * g[k][i].w;
	}
	return son[k];
}

void doit()
{
	ans = 0;
	memset(son, 0, sizeof(son));
	dfs(1, 1);
	double output = (double)ans * 2.0 / (double)(n*(n-1)) ;
	printf("%.2f\n", output);
}


int main()
{
	LL case_num;
	scanf("%lld", &case_num);
	while (case_num--)
	{
		init();
		doit();
	}
	return 0;
}