本文共 2112 字，大约阅读时间需要 7 分钟。

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 思路：

引：如果暴力枚举两点再求距离是显然会超时的。转换一下思路，我们可以对每条边，求所有可能的路径经过此边的次数：设这条边两端的点数分别为A和B，那 么这条边被经过的次数就是AB，它对总的距离和的贡献就是(AB此边长度)。我们把所有边的贡献求总和，再除以总路径数N(N-1)/2，即为最 后所求。

每条边两端的点数的计算，实际上是可以用一次dfs解决的。任取一点为根，在dfs的过程中，对每个点k记录其子树包含的点数（包括其自身），设点数为a[k]，则k的父亲一侧的点数即为N-a[k]。这个统计可以和遍历同时进行。故时间复杂度为O(n)。。具体解释看代码

代码如下： #include #include #include #include #include #include using namespace std;

const int maxx=1e4+10;

double dp[maxx]; int sum[maxx];//记录经过某个点的次数 struct node{ int v; int len; }; vectorvec[maxx];//树形dp的题目一般用vector存储是最好的，比起邻接表来，它要快得多、 int n;

void init()//初始化

{ for(int i=0;i<=n;i++) vec[i].clear(); memset(sum,0,sizeof(sum)); memset(dp,0,sizeof(dp)); }

void dfs(int top,int f)

{ sum[top]=1; for(int i=0;i<vec[top].size();i++) { int s=vec[top][i].v; int len=vec[top][i].len; if(s==f) continue; dfs(s,top); sum[top]+=sum[s]; dp[top]+=dp[s]+(sum[s](n-sum[s]))(double)len; } } int main() { int u,v,len,t; cin>>t; while(t–) { cin>>n; init(); for(int i=1;i<=n-1;i++) { node p1,p2; scanf("%d%d%d",&u,&v,&len); p1.v=u; p2.v=v; p1.len=p2.len=len; vec[v].push_back(p1); vec[u].push_back(p2); } dfs(0,-1); int dis=n*(n-1)/2;//总的条数 printf("%1lf\n",(double) dp[0]/dis); }

}

树形dp是建立在树的基础上的，因此树的一些概念啥的我们要清楚，还有就是多画图，自己多模拟，多做题

努力加油a啊，(^o)/~

转载地址：http://mzxvi.baihongyu.com/