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 (d 01 + d 02 + d 03 + d 04 + d 12 +d 13 +d 14 +d 23 +d 24 +d 34)/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
题意:就是求上面那个式子的值,看式子和图就能懂。
题解:用树形dp跑,把每条边用的次数算出来,然后乘这条边的值就好了,用过的次数=该边的尾节点后边所连点的个数(包括该点)*该边的尾节点前面所连点的个数(不包括该点),然后用次数乘价值,最后把每条边所求加和,就可以了。
注意:不能用cin,cout 输入输出流,要用标准输入,输出,要不然会T(超时)。 上代码:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAX = 1e5;
struct hh{
int u,v;
double w;
int nt;
}a[MAX];//用来保存树
int head[MAX];
double num[MAX];
int cnt,n;
double ar;
void add(int u,int v,double w){//建树,记住就好了
a[cnt].u=u;
a[cnt].v=v;
a[cnt].w=w;
a[cnt].nt=head[u];
head[u]=cnt++;
}
void dfs(int foot,int fz){
num[foot]=1;
for (int i = head[foot]; ~i; i = a[i].nt){
int vv=a[i].v;
int ww=a[i].w;
if(vv!=fz){
dfs(vv,foot);
num[foot]+=num[vv];//统计用的次数
ar+=num[vv]*(n-num[vv])*ww;//后边*前边*价值,然后相加
}
}
}
int main(){
int t;
scanf("%d", &t);
while(t--){
memset(head,-1,sizeof(head));//存为-1,建图常用
memset(num,0,sizeof(num));//初始化
cnt=0;
scanf("%d",&n);
for (int i = 0; i < n-1;i++){
int u,v;
double w;
scanf("%d%d%lf",&u,&v,&w);
add(u,v,w);//建立双向 ,看题目里的图就知道
add(v,u,w);
}
ar=0;
dfs(0,-1);
printf("%.7f\n",ar/(1.0*n*(n-1)/2.0));//输出注意精度
}
return 0;
}