飞机票：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1911

题意：就是给你一颗树包含n个点(n<=10000)和边权值，求任意两点之间的平均距离，即任意两点距离和除以有多少个点对。

分析：容易计算点对数就是n*(n-1)/2，如何求总距离和，可以考虑两个点，假设为u，v，且有条边(u,v)权值为x，这样我们就可以知道，x肯定要用u子节点的个数*v子节点的个数(其中子节点代表u下面所有的节点个数)，包含各自本身，因为u子节点到v子节点必定要经过(u,v）这条边，这样的话我们就可以递归处理了，假设当前节点为u，它的子节点数加它本身有p个，则它父亲节点v那一块就有n-p个。然后总距离就加上p*(n-p)*x了。最后啪啪啪，就可以AC了

/*
Author:Chieh
Because Of Coding
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define LL long long
#define INF 1e9
#define EPS 1e-9
using namespace std;
const int maxn=12345;
int T;
vector<int> V[maxn];
vector<int> G[maxn];
int n;
void init()
{
    int u, v,w;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        V[i].clear();
        G[i].clear();
    }
    for(int i=1; i<n; i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        u++;
        v++;
        V[u].push_back(v);
        V[v].push_back(u);
        G[u].push_back(w);
        G[v].push_back(w);
    }
}
double ans;
int DFS(int now,int fa,double val)
{
    int chi=1;
    for(int i=0; i<V[now].size(); i++)
    {
        int u=V[now][i];
        int w=G[now][i];
        if(u==fa)continue;
        chi+=DFS(u,now,w);
    }
    int oth=n-chi;
    ans=ans+(val*oth*chi);
    return chi;
}
void play()
{
    ans=0;
    DFS(1,-1,0);
    double fm=(n*(n-1)/2);
    printf("%.10f\n",ans/fm);
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        init();
        play();
    }
    //cout << "Hello world!" << endl;
    return 0;
}