给定一棵树，计算树中两个顶点之间的平均距离。

输入：

5

1 2 6

1 3 3

1 4 7

4 5 2

输出：8.600000

#include<bits/stdc++.h>
using namespace std;
int n;
int ans;
vector<pair<int,int> > vec[100001];
int vis[100001],dis[100001];
int jc(int x)
{
	int anss=0;
	for(int i=1;i<=x;i++)
	{
		anss+=i;
	}
	return anss;
}
void dfs(int x)
{
	vis[x]=1;
	for(int i=0;i<vec[x].size();i++)
	{
		int y=vec[x][i].first;
		{
			if(vis[y]==0)
			{
				dfs(y);
				dis[x]+=dis[y];
			}
		}
	}
}
void dfs2(int x)
{
	vis[x]=2;
	for(int i=0;i<vec[x].size();i++)
	{
		int y=vec[x][i].first;
		{
			if(vis[y]==1)
			{
				//printf("%d %d %d\n",dis[x],dis[y],vec[x][i].second);
				ans+=(n-min(dis[x],dis[y]))*min(dis[x],dis[y])*vec[x][i].second;
				dfs2(y);
			}
		}
	}
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int u,v,c;
		scanf("%d%d%d",&u,&v,&c);
        vec[u].push_back(make_pair(v,c));
        vec[v].push_back(make_pair(u,c));
	}
	for(int i=1;i<=n;i++) dis[i]=1;
	dfs(1);
	dfs2(1);
	double js=ans*1.0/(n*(n-1)/2)*1.0;
	printf("%.6lf\n",js);
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}