Pentru a rezolva problema putem aplica o strategie de tip greedy în care la fiecare pas luăm cele mai mici două grămezi şi le reunim. Pentru a se încadra în timp şi pentru a fi corect e necesară folosirea unui multiset şi a tipului de date long long.

h2.

h2. 'F. Average distance':http://acm.tju.edu.cn/toj/vcontest/showp9268_F.html
 
După cum îi spune şi numele această problemă ne cere sa calculăm costul mediu al muchiilor dintr-un arbore.
 
Pentru a rezolva problema observăm că costul mediu e egal cu suma costurilor drumurilor din arbore împărţită la numărul total de drumuri.
Numărul de drumuri e egal cu $N*(N-1)/2$ (Combinări de $N$ luate câte doua, fiecare drum fiind definit de 2 noduri).
Pentru a calcula suma costurilor drumurilor ne interesează fiecare muchie în câte drumuri apare.
O muchie $(A,B)$ apare in orice drum definit de un nod din subarborele lui A(inclusiv A) şi de un nod care nu e in subarborele lui A.
 
==code(cpp)
//Cristian Lambru
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
 
#define MaxN 110000
#define ll long double
 
int N;
int T[MaxN],Fii[MaxN],viz[MaxN];
vector<pair<int,int> > A[MaxN];
 
void citire(void)
{
    int a,b,c;
 
    scanf("%d",&N);
    for(int i=1;i<N;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        A[a].push_back(make_pair(b,c));
        A[b].push_back(make_pair(a,c));
    }
}
 
inline void DF(int nod)
{
    viz[nod] = 1;
    Fii[nod] = 1;
 
    for(int i=0;i<A[nod].size();i++)
        if(!viz[A[nod][i].first])
        {
            DF(A[nod][i].first);
            T[A[nod][i].first] = nod;
            Fii[nod] += Fii[A[nod][i].first];
        }
}
 
inline double suma(void)
{
    ll sum = 0;
 
    for(int i=0;i<=N;i++)
        for(int j=0;j<A[i].size();j++)
            if(A[i][j].first > i)
            {
                if(T[i] != A[i][j].first)
                    sum += (ll)A[i][j].second*Fii[A[i][j].first]*(N-Fii[A[i][j].first]);
                else
                    sum += (ll)A[i][j].second*Fii[i]*(N-Fii[i]);
            }
 
    return sum/((ll)N*(N-1)/2);
}
 
inline void sterge(void)
{
    for(int i=0;i<N;i++)
        A[i].clear(), Fii[i] = T[i] = viz[i] = 0;
}
 
int main()
{
    //freopen("test.txt","r",stdin);
    int T;
    scanf("%d",&T);
 
    for(int i=1;i<=T;i++)
    {
        citire();
        DF(0);
 
        printf("%lf\n",suma());
        sterge();
    }
 
    return 0;
}
==