2.道路修建
描述 Description
liouzhou_101最悲痛的回忆就是NOI2011的道路修建，当时开了系统堆栈，结果无限RE…
出于某种报复心理，就把那题神奇了一下：
在 Z星球上有N个国家，这N个国家之间只能建造N-1条道路且全部建完这N-1条道路后这N个国家相互连通，修建每条道路都有相应的花费。但是他们都很吝啬，于是决定只随机选出两个不同的国家(为了国家的平等，当然这两个国家是无顺序可言的)，建造该建造的道路，使得这两个国家相互连通，自然费用越少越 好。然后问你，在所有情况中，修建道路花费的平均值。
假若您认为本题题目叙述太渣，那就形象地描述一遍：给出一棵边上带权的树，求任意两个不同的点的距离的期望值。
输入格式 InputFormat
第一行包括一个正整数N，N表示国家的数量。
接下来N-1行每行包括三个正整数x、y和w，表示国家x和国家y之间有一条花费为w的道路。
输出格式 OutputFormat
仅一行，包含一个最简分数，格式为A/B，详见样例。
样例输入 SampleInput [复制数据]
4
1 2 1
1 3 1
1 4 1
样例输出 SampleOutput [复制数据]
3/2
数据范围和注释 Hint
对于这组测资，共存在6种情况：
①(1,2) 距离 1； ②(1,3) 距离 1；
③(1,4) 距离 1； ④(2,3) 距离 2；
⑤(2,4) 距离 2； ⑥(3,4) 距离 2；
所以平均值为(1+1+1+2+2+2)/6=3/2。
30%的数据，满足n<=1,000；
50%的数据，满足n<=10,000；
100%的数据，满足1<=n<=100,000，1<=w<=1,000。
时间限制 TimeLimitation
1s
解：随便找个点dfs，假设节点y下有s[y]个点（包括y），他的父节点为t，通过这条路就有s[y]*(n-s[y]）次，统计一下即可。
注意：全开long long
来源：“扫地”杯III NOIP2012模拟赛 day1 第二题
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define man 101000
#define ll long long
using namespace std;
ll n;
struct edge
{
ll next,to,dis;
}e[man*];
ll s[man];
bool vis[man];
ll sum=;
ll head[man*],num=;
void add(int from,int to,int dis)
{
e[++num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num;
}
ll gcd(ll a,ll b)
{
if(b==)
return a;
else return gcd(b,a%b);
}
void dfs(ll t)
{
s[t]=;vis[t]=;
for(int i=head[t];i;i=e[i].next)
{
ll to=e[i].to;
if(!vis[to])
{
dfs(to);
sum+=e[i].dis*(n-s[to])*s[to];
s[t]+=s[to];
}
}
}
int main()
{ freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
scl(n);
for(int i=;i<n;i++)
{
int x,y,z;
sc(x);sc(y);sc(z);
add(x,y,z);
add(y,x,z);
}
dfs();
n=n*(n-)/;
if(n==)
n=;
ll ans=gcd(sum,n);
printf("%lld/%lld",sum/ans,n/ans);
return ;
}