# Average distance

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 682    Accepted Submission(s): 244
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

Source

bapc2007

Recommend

lcy   |   We have carefully selected several similar problems for you:  2378 2379 2377 2380 2381

 16447376 2016-03-06 09:40:59 Accepted 2376 312MS 4540K 2093 B C++ czy
 1 #include <cstdio>
2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <stack>
6 #include <cctype>
7 #include <vector>
8 #include <cmath>
9 #include <map>
10 #include <queue>
11
12 #define ll long long
13 #define N 10005
14 #define eps 1e-8
15
16 using namespace std;
17
18 int T;
19 double tot[N];
20 double cou[N];
21 double num;
22 int n;
23
24 struct PP
25 {
26     int to;
27     double val;
28 };
29
30 vector<PP>Edge[N];
31
32 PP te;
33
35 {
36     te.to = to;te.val = val;
37     Edge[from].push_back(te);
38     te.to = from;te.val = val;
39     Edge[to].push_back(te);
40 }
41
42 void dfs(int now,int fa)
43 {
44     unsigned int i;
45     PP nt;
46     cou[now] = 1;
47     for(i = 0;i < Edge[now].size();i++){
48         nt.to = Edge[now][i].to;
49         nt.val = Edge[now][i].val;
50         if(nt.to == fa){
51             continue;
52         }
53         dfs(nt.to,now);
54         tot[now] = tot[now] + tot[nt.to] + (n-cou[nt.to]) * cou[nt.to] * nt.val;
55         cou[now] = cou[now] + cou[nt.to];
56         //printf("  now = %d i=%d to=%d tot=%.6f cou=%.6lf\n",now,i,nt.to,tot[now],cou[now]);
57     }
58     //printf(" i=%d tot=%.6f cou=%.6f\n",now,tot[now],cou[now]);
59 }
60
61 int main()
62 {
63     //freopen("in.txt","r",stdin);
64     scanf("%d",&T);
65     int i;
66     int from,to;
67     double val;
68     for(int ccnt=1;ccnt<=T;ccnt++){
69     //while(scanf("%lf%lf%lf%lf",&a[0],&a[1],&a[2],&a[3])!=EOF){
70         scanf("%d",&n);
71         memset(tot,0,sizeof(tot));
72         memset(cou,0,sizeof(cou));
73         num = 1.0 *n*(n-1)/2;
74         for(i=0;i<=n;i++){
75             Edge[i].clear();
76         }
77         for(i=1;i<=n-1;i++){
78             scanf("%d%d%lf",&from,&to,&val);
80         }
81         dfs(0,-1);
82         //for(i=0;i<n;i++){
83          //   for(int j=0;j<Edge[i].size();j++){
84          //       printf(" i=%d to=%d val=%.6lf\n",i,Edge[i][j].to,Edge[i][j].val);
85          //   }
86        // }
87         for(i=0;i<n;i++){
88             //printf(" i=%d tot=%.6f cou=%.6f\n",i,tot[i],cou[i]);
89         }
90         printf("%lf\n",tot[0]/num);
91     }
92     return 0;
93 }

## HDU 4712 Hamming Distance (随机函数)

Hamming Distance Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1806    Accepted Submission(s): 714 Problem Description (From wikipedia) For binary strings a and b the Hamming distance is equal

## hdu 5903 Square Distance(dp)

Problem Description A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not. Hamming distanc

## hdu 4712 Hamming Distance（随机数法）

d.汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量, 我们以d(x,y)表示两个字x,y之间的汉明距离.对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离. 给出N个串,求出其中最小的汉明距离(其中某2个串的汉明距离是最小的). s.随机数法... c.能不能过,看脸... #include<iostream> #include<stdio.h> #include<string.h> #inc

## HDU 5903 Square Distance

$dp$预处理,贪心. 因为$t$串前半部分和后半部分是一样的,所以只要构造前一半就可以了. 因为要求字典序最小,所以肯定是从第一位开始贪心选择,$a,b,c,d,...z$,一个一个尝试过去,如果发现某字符可行,那么该位就选择该字符. 第$i$位选择字符$X$可行的条件: 记这一位选择字符$X$的情况下,对$dis$的贡献为$Q$,$1$至$i-1$位对$dis$贡献和为$F$: 如果第$i+1$位至第$\frac{n}{2}$位,对$dis$的贡献可以凑出$m-Q-F$,那么该位选择$X$可

## Soj题目分类

-----------------------------最优化问题------------------------------------- ----------------------常规动态规划  SOJ1162 I-Keyboard  SOJ1685 Chopsticks SOJ1679 Gangsters SOJ2096 Maximum Submatrix  SOJ2111 littleken bg SOJ2142 Cow Exhibition  SOJ2505 The County

## Cracking The Vigenere Cipher

In order to crack "Vigenere Cipher" under the circumstance that the key length can be only 3, 4 or 5, I used frequency analysis to find possible keys and compared the Euclidean distance of all candidate keys calculated with "Relative freque

## Isolation-based Anomaly Detection

Anomalies are data points that are few and different. As a result of these properties, we show that, anomalies are susceptible to a mechanism called isolation. This paper proposes a method called Isolation Forest (iForest) which detects anomalies pur