原题：http://acm.hdu.edu.cn/showproblem.php?pid=2376
经典问题，求的是树上任意两点和的平均值。
这里我们不能枚举点，这样n^2的复杂度。我们可以枚举每一条边，设这条边的端点分别为A、B，则通过这条边的路径总数为与A点相连的端点数乘以与B点相连的端点数，再乘以这条边的权值，将所有的和相加，最后除以n*(n-1)/2就可以了（除以2是因为这里每条边重复计算了两次）。
这里统计求和的时候，一遍深搜就可以了，需要注意的是，假设某个点子树所包含点的个数为k，则这条边另一个端点所包含的点的个数的为n-k。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 11111; 4 struct node{ 5 int v;//终点 6 int w;//权值 7 }; 8 vector<node> tree[maxn]; 9 long long dp[maxn]; 10 int sum[maxn];//统计每个点子树所包含点的个数 11 int n; 12 void dfs(int cur,int father){ 13 sum[cur] = 1; 14 for(int i = 0;i<tree[cur].size();i++){ 15 int son = tree[cur][i].v; 16 long long len = tree[cur][i].w; 17 if(father == son) 18 continue; 19 dfs(son,cur); 20 sum[cur] += sum[son]; 21 dp[cur] += dp[son]+sum[son]*(n-sum[son])*len; 22 } 23 } 24 int main(){ 25 int t; 26 scanf("%d",&t); 27 while(t--){ 28 scanf("%d",&n); 29 for(int i = 0;i<n;i++) 30 tree[i].clear(); 31 memset(dp,0,sizeof(dp)); 32 memset(sum,0,sizeof(sum)); 33 int u,v,w; 34 for(int i = 0;i<n-1;i++){ 35 scanf("%d%d%d",&u,&v,&w); 36 node t1,t2; 37 t1.v = v; 38 t1.w = w; 39 t2.v = u; 40 t2.w = w; 41 tree[u].push_back(t1); 42 tree[v].push_back(t2); 43 } 44 //以任意一点为根进行搜索 45 dfs(0,-1); 46 printf("%lf ",dp[0]*2.0/n/(n-1)); 47 } 48 return 0; 49 }