HDU - 2376

Average distance

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1980 Accepted Submission(s): 717
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 (d01 + d02 + d03 + d04 + d12 +d13 +d14 +d23 +d24 +d34)/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

题目就是求所有路径之和，再除以总的边的数量即可。

这道题比较巧妙，就是我们分析每一条边的贡献值，每一条边的贡献就是左右两个端点的size之积再乘以这条边的长度即可。

所以我们用dfs一遍，求出每个点的子树大小即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e4+10;
int T,n,sz[N],res;
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	sz[x]=1;
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		dfs(to[i],x);	sz[x]+=sz[to[i]];
		res+=(n-sz[to[i]])*sz[to[i]]*w[i];
	}
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		memset(head,0,sizeof head);	res=tot=0;
		scanf("%lld",&n);
		for(int i=1;i<n;i++){
			int a,b,c; scanf("%lld %lld %lld",&a,&b,&c);
			a++;	b++;	add(a,b,c);	add(b,a,c);
		}
		dfs(1,0);
		printf("%.7lf\n",res*2.0/n/(n-1));
	}
	return 0;
}