Average distance

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1830 Accepted Submission(s): 659
Special Judge
Problem Description
Given a tree, calculate the average distance between two vertices in the tree. For example, the average distance between two vertices in the following tree is $(d_{01} + d_{02} + d_{03} + d_{04} + d_{12} +d_{13} +d_{14} +d_{23} +d_{24} +d_{34})/10 = (6+3+7+9+9+13+15+10+12+2)/10 = 8.6$.

Input
On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:
One line with an integer n (2 <= n <= 10 000): the number of nodes in the tree. The nodes are numbered from 0 to n - 1.
n - 1 lines, each with three integers a (0 <= a < n), b (0 <= b < n) and d (1 <= d <= 1 000). There is an edge between the nodes with numbers a and b of length d. The resulting graph will be a tree.
Output
For each testcase:
One line with the average distance between two vertices. This value should have either an absolute or a relative error of at most $10^{-6}$
Sample Input
1
5
0 1 6
0 2 3
0 3 7
3 4 2
Sample Output
8.6

引：如果暴力枚举两点再求距离是显然会超时的。转换一下思路，我们可以对每条边，求所有可能的路径经过此边的次数：设这条边两端的点数分别为A和B，那 么这条边被经过的次数就是AB，它对总的距离和的贡献就是(AB此边长度)。我们把所有边的贡献求总和，再除以总路径数N(N-1)/2，即为最 后所求。

下面是AC的代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;

int T;
int n;
struct Node{
    int value;
    int point;
};
double ans[10000+5];
double sum[10000+5];
vector<Node> node[10000+5];

void dfs(int son,int father){
    sum[son]=1;
    for(int i=0;i<node[son].size();i++){
        int p=node[son][i].point;
        int v=node[son][i].value;
        if(p==father){continue;}
        dfs(p,son);
        sum[son]+=sum[p];
        ans[son]+=ans[p]+sum[p]*(n-sum[p])*v;
    }
}

void solve(){
    scanf("%d",&n);
    int a,b,d;
    for(int i=0;i<n;i++){
        node[i].clear();
    }
    memset(ans,0,sizeof(ans));
    memset(sum,0,sizeof(sum));
    for(int i=0;i<n-1;i++){
        scanf("%d%d%d",&a,&b,&d);
        Node temp;
        temp.point=b;
        temp.value=d;
        node[a].push_back(temp);
        temp.point=a;
        node[b].push_back(temp);
    }
    dfs(0,-1);
    double number=n*(n-1)/2;
    //cout<<ans[0]/number<<endl;
    printf("%.7f\n",ans[0]/number);
}

int main()
{
   scanf("%d",&T);
   while(T--){
     solve();
   }
   return 0;
}