shunfurh 于 2017.01.04 22:13 提问

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

1个回答

caozhy      2017.01.12 00:44

hdu 2376(求树上任意两点之间距离之和的平均值）

hdu 2376 Average distance DFS 求树上任意两点距离和
hdu 2376 Average distance DFS 求树上任意两点距离和 题目链接：hdu 2376 Average distance 题意:标题都已经说明了题意了。求树上任意两点距离和的平均值。 分析：分析过程和《 hdu 5723 Abandoned country 最小生成树+DFS》中求树上任意两点距离之和是完全一样的。思路就是先求出每条边两端的点的个数，然后对于每条边，
HDU 2376(树上任意2点间的距离)

HDU 5723 Abandoned country (并查集 + DFS+求解树上任意两点间的距离的平均值)
Abandoned country Time Limit: 8000/4000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 293    Accepted Submission(s): 85 Problem Description An abandone
poj1741 Tree (求树上任意两点之间权值和小于k的个数）（树分治）

HDU2376Average distance(树形dp|树上任意两点距离和的平均值)

poj 1986 LCA 求树上任意两节点距离

【OI杂记】求二叉树上任意两点的最短路径上的边权最大值

（HDU 5723）Abandoned country <最小生成树 + 树上所有两点之间的距离的期望> 多校训练1
Abandoned country Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 4941 Accepted Submission(s): 1249Problem Description An abandoned countr
POJ 2874 LCA 树上任意两点距离