题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5723
多校第一场就分数爆零，这是我们队比赛里面唯一过的一题TT。
题意：给我们n个点和m条边，然后问我们最小生成树以及最小生成树上两两点之间距离的期望值。
期望值很显然就是所有两两点之间的距离和除上总共的选择数(n*(n-1)/2)。
一开始没有看见每一条边的权值都是唯一的，想了好久如果存在不同的最小生成树的话该怎么搞=.=，既然权值唯一，那么最小生成树就唯一，期望值也就唯一，接下来算期望，这个也不算太简单，如果每一对我们都去搜一遍肯定超时，所以我们必须得转换这个问题，我们可以思考一条边用到了几次。首先，如果一条边的一侧有sum[i]个点，那么另一边就有n-sum[i]个点，那么这两边的组合数就是sum[i]*(n-sum[i])也就是说这条就用 这么多次。因为是树的结构，我们从任意一点出发，只要不走回头路，我们就可以遍历整棵树，我看有些人用到了vis数组来记录，其实是完全没有必要的，我们一边搜索一边记录就可以得到答案。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100000+5;
LL set[maxn], n;
int sum[maxn];
double dp[maxn];
struct Edge
{int u,v,w;Edge(int _u,int _v,int _w):u(_u),v(_v),w(_w){}
};
struct Node
{int v,len;Node(int _v,int _len) : v(_v), len(_len){}
};
vector<Edge> edge;
vector<Node> vec[maxn];
int cmp(Edge a,Edge b)
{return a.w < b.w;
}
inline void addEdge(int u,int v,int w)
{vec[u].push_back(Node(v, w));vec[v].push_back(Node(u, w));
}
inline int find(int r)
{return set[r]==r? r : set[r]=find(set[r]);
}
inline LL merge(int a,int b,int w)
{int x = find(a);int y = find(b);if(x == y) return 0;set[x] = y;addEdge(a, b, w);return (LL)w;
}
LL Kruskal()
{sort(edge.begin(), edge.end(), cmp);LL ans = 0;for(int i=0; i<edge.size(); i++)ans += merge(edge[i].u, edge[i].v, edge[i].w);return ans;
}
void dfs(int root,int father)
{sum[root] = 1;for(int i = 0;i < (int)vec[root].size();i++){int son = vec[root][i].v;int len = vec[root][i].len;if(son == father)continue;dfs(son,root);sum[root] += sum[son];dp[root] += dp[son] + (double)(sum[son] * (n - sum[son])) * len;}
}
int main()
{//freopen("1001.in","r",stdin);int T;scanf("%d", &T);while(T--){int m;scanf("%I64d%d", &n, &m);edge.clear();for(int i=0; i<m; i++){int u,v,w;scanf("%d%d%d", &u,&v,&w);edge.push_back(Edge(u,v,w));}for(int i=1; i<=n; i++) set[i] = i,vec[i].clear();LL ans = Kruskal();memset(sum,0,sizeof(sum));memset(dp,0,sizeof(dp));dfs(1, 0);double tmp = (n*(n-1))/2;printf("%I64d %.2lf\n", ans, (double)dp[1]/tmp);}
}