2 shunfurh 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
caozhy   Ds   Rxr 2017.01.12 00:44
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
hdu 2376(求树上任意两点之间距离之和的平均值)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2376 思路: 引:如果暴力枚举两点再求距离是显然会超时的。转换一下思路,我们可以对每条边,求所有可能的路径经过此边的次数:设这条边两端的点数分别为A和B,那 么这条边被经过的次数就是A*B,它对总的距离和的贡献就是(A*B*此边长度)。我们把所有边的贡献求总和,再除以总路径数N*(N-1)/2,即
hdu 2376 Average distance DFS 求树上任意两点距离和
hdu 2376 Average distance DFS 求树上任意两点距离和 题目链接:hdu 2376 Average distance 题意:标题都已经说明了题意了。求树上任意两点距离和的平均值。 分析:分析过程和《 hdu 5723 Abandoned country 最小生成树+DFS》中求树上任意两点距离之和是完全一样的。思路就是先求出每条边两端的点的个数,然后对于每条边,
HDU 2376(树上任意2点间的距离)
题目链接 题意:求树上任意2点之间距离的期望 dfs跑一遍,统计每条边的贡献#include<bits/stdc++.h> using namespace std;#define cl(a,b) memset(a,b,sizeof(a)) #define LL long longconst int maxn = 11005; const int inf = 1 << 23;struct Edg
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的个数)(树分治)
题意:给你n个节点的树和k,问在这个树上两点之间最近距离小于k的情况有多少种? 思路: 看了两天题解(有些还写错)和一篇关于树分治的论文分治算法在数的路径问题中的应用才知道这是一类我从来没有做过的思想,在树上利用重心分治的搞一下把O(n)的步骤优化到O(logn). 先分析: 假定选择一点1为根,那其他点到根的最短距离就有两种情况。 其一,它们在根的不同分支上,那他们的最近距离就是它们到它
HDU2376Average distance(树形dp|树上任意两点距离和的平均值)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2376 思路: 引:如果暴力枚举两点再求距离是显然会超时的。转换一下思路,我们可以对每条边,求所有可能的路径经过此边的次数:设这条边两端的点数分别为A和B,那 么这条边被经过的次数就是A*B,它对总的距离和的贡献就是(A*B*此边长度)。我们把所有边的贡献求总和,再除以总路径数N*(N-
poj 1986 LCA 求树上任意两节点距离
传送门 题意:就是一棵树,求节点距离。 思路:如果t是u,v的最近公共祖先,那么d[u,v]=d[u,root]+d[v,root]-2*d[t,root],就根据这个来搞之。 每到一个点然后遍历所有询问。。。果断超了,之后便用vector来存询问,也超时,然后find函数压缩了下路径就过了。。。。。。。 #include #include #include #include using
【OI杂记】求二叉树上任意两点的最短路径上的边权最大值
给出一棵树,每条边有一边权。 对于任意给定的两点,求,此两点的最短路径上,边权的最大值。   对于下图: 蓝圈中任意一点与红圈中任意一点的路径上的最大边必定是8。   根据这个现象,可以把上述的树重建成如下图所示。 新图的叶子结点为原图的所有结点,内部结点为原图的边权,建边顺序又下小到大。 如图所示: 新图的红色编号为原图的结点编号,蓝色编号为原图
(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 树上任意两点距离
本题说了是无环图,所以就是一片森林了。 而对于树上的任意两点,我们可以用LCA求其距离。距离为两个子节点到根的距离和减去最近祖先到根的距离的2倍。具体画图便可看出来。   并且图是无向图,所以LCA时需要进行标记 POJ 1986同这道题 基本一样 /* ID: CUGB-wwj PROG: LANG: C++ */ #include #include #include #incl