思路：
引：如果暴力枚举两点再求距离是显然会超时的。转换一下思路，我们可以对每条边，求所有可能的路径经过此边的次数：设这条边两端的点数分别为A和B，那 么这条边被经过的次数就是A*B，它对总的距离和的贡献就是(A*B*此边长度)。我们把所有边的贡献求总和，再除以总路径数N*(N-1)/2，即为最 后所求。
每条边两端的点数的计算，实际上是可以用一次dfs解决的。任取一点为根，在dfs的过程中，对每个点k记录其子树包含的点数（包括其自身），设点数为a[k]，则k的父亲一侧的点数即为N-a[k]。这个统计可以和遍历同时进行。故时间复杂度为O(n)。
#include<bits/stdc++.h> using namespace std ; #define ll long long const int maxn = 10005; int sum[maxn] , n; ll dp[maxn]; struct no { int v,w; }t1,t2; vector<no>tree[maxn] ; void dfs(int cur , int father) { sum[cur] = 1 ; for(int i = 0 ; i < tree[cur].size() ; i++) { int son = tree[cur][i].v; ll len = tree[cur][i].w; if(father == son) continue; dfs(son , cur) ; sum[cur]+=sum[son]; dp[cur]+=dp[son] + (n-sum[son])*sum[son]*len; } } int main( ) { int u,v,w,t; scanf("%d",&t); while(t--) { scanf("%d",&n); for(int i=0 ; i<n ; i++) tree[i].clear(); memset(sum,0,sizeof(sum)); memset(dp,0,sizeof(dp)); for(int i=0 ; i<n-1 ; i++) { scanf("%d%d%d",&u,&v,&w); t1.v=v; t1.w=w; t2.v=u; t2.w=w; tree[u].push_back(t1); tree[v].push_back(t2); } dfs(0,-1); printf("%f ",dp[0]*2.0/n/(n-1)); } return 0; }