2 shunfurh shunfurh 于 2016.12.31 19:19 提问

Average distance

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

2个回答

caozhy
caozhy   Ds   Rxr 2016.12.31 19:16
已采纳
sinat_37181010
sinat_37181010   2016.12.31 21:42

你可以关注下 ITIL先锋这个微信公众号 上面每天会更新IT行业最前沿资讯和各种类别的IT资料,感觉工作学习都比较有用

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Fast marching on 3D meshes with diffusion distance
与fast marching on 3D meshes with euclidian distance 不同(http://blog.csdn.net/seamanj/article/details/52077197), 基于欧氏距离是在欧氏空间算geodesic的距离, 而基于diffusion distance,在是diffusion space里面采用类似geodesic的算法, 只不过这里
hdu2376 Average distance
题意:求一个树上任意两点距离的平均值。 思路:如果枚举任意两个点来求,一定会超时,不如换个思路,求每个边的贡献次数边权值的和就是任意两点距离的总和。然后除以总路径数之和n(n-1). 而每个边的贡献次数等于每个边两边顶点个数的乘积(这个自己举个例子),然后这题就可以转换成在一个有根树里,求每个顶点构成子树的节点个数,一遍dfs就可以得到,dfs写法见代码.选根这题,没有特定要求,可以任取。最后注
average diffusion distance
average diffusion distance implemented in matlab
三维模型上两点之间的测地线距离 Geodesic Distance
该资源提供了计算测地线距离的lib、dll库和要包含的头文件,还包含了实例代码。没有源文件。 该资源是2005 SIGGRAPH中Fast Exact and Approximate Geodesics on Meshes文章的实现,其作者是Vitaly Surazhsky, Tatiana Surazhsky, Danil Kirsanov, Steven J. Gortler and Hugues Hoppe。
Learning_PN_Toolbox
学习Petri Net必备资料 After simulation ends, the global performance indices described in the Scope section are stored by the PN Toolbox and can be visualized by using the Performance menu. Besides these, there are also a number of global indices for which the current values are not defined. The following two tables present the complete lists of global indices associated with the places (displayed by the Place Indices command) and the transitions (displayed by the Transition Indices command), respectively: - for a transition: • Service Sum: total number of firings; • Service Distance: average value of the current index Service Distance; • Service Rate: average frequency of firings (inverse of Service Distance); • Service Time: average value of the current index Service Time; • Utilization: average value of the current index Utilization; - for a place: • Arrival Sum: total number of arrived tokens; • Arrival Distance: average value of the current index Arrival Distance; • Arrival Rate: average frequency of token-arrivals (inverse of Arrival Distance); • Throughput Sum: total number of departed tokens; • Throughput Distance: average value of the current index Throughput Distance; • Throughput Rate: average frequency of token-departures (inverse of Throughput
Hausdorff distance的模板匹配
 一、  Hausdorff距离匹配算法及代码 http://blog.csdn.net/holamirai/article/details/48351019 二、http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html#whatis 三、OpenCV 谈openc
LeetCode 346. Moving Average from Data Stream(数据流移动平均值)
原题网址:https://leetcode.com/problems/moving-average-from-data-stream/ Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window. For exampl
欧氏距离(Euclidean distance)
欧氏距离定义: 欧氏距离( Euclidean distance)是一个通常采用的距离定义,它是在m维空间中两个点之间的真实距离。在二维和三维空间中的欧式距离的就是两点之间的距离,二维的公式是 d = sqrt((x1-x2)^+(y1-y2)^) 三维的公式是 d=sqrt(x1-x2)^+(y1-y2)^+(z1-z2)^) 推广到n维空间,欧式距离的公式是 d=sqrt( ∑(xi1-xi2
【hdu 2376】Average distance
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=2376【题意】 让你计算树上任意两点之间的距离的和. 【题解】 算出每条边的两端有多少个节点设为num1和num2; 这条边的边权为w; 答案累加上w*num1*num2; 然后总的答案除n*(n-1)/2; 【完整代码】#include <bits/stdc++.h> us
图像处理(四)图像分割(2)测地距离Geodesic图割
参考文献:《Geodesic Matting: A Framework for Fast Interactive Image》 算法原理:基于测地距离的图像分割属于一种图论的分割算法。图论分割算法:即把图像上的每个像素点当做图的顶点,图的每个顶点有四个邻接顶点(每个像素点有四个邻接像素点,除边界点),每两个邻接像素点用相应的边连接,边的长度与两个像素点间的相似度有关(测地距离),而非采用简单的欧