题面：http://acm.hdu.edu.cn/showproblem.php?pid=2376
题意：计算树上任意两点距离和的平均值。
解法：树形dp
这是一个简单基础经典的树形dp。
我们考虑计算每条边的贡献，对于一条边u->v假设u的一侧有m个结点，v的一侧有n个结点，那么这两边的结点要想互通，必然要经过这一条边，所以这一条边的贡献就是m乘以n。
所以我们只需要一遍dfs，计算出每条边的贡献和即可。
具体来说，我们需要记录每个结点为根的子树所含结点i个，那么另一侧的结点个数必然是n-i个，每次相加即可。
我们把所有边的贡献求总和，再除以总路径数N * (N - 1) / 2，即为最后所求。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
const int maxn = 1e4 + 10;
struct node{
int to;
ll cost;
};
vector<node> tree[maxn];
ll sum[maxn], dp[maxn];
int n;
void dfs(int now, int fa)
{
sum[now] = 1;
for(auto idx: tree[now])
{
if(idx.to == fa) continue;
dfs(idx.to, now);
sum[now] += sum[idx.to];
dp[now] += dp[idx.to] + sum[idx.to] * (n - sum[idx.to]) * idx.cost;
}
}
int main()
{
int cas;
scanf("%d", &cas);
while(cas--)
{
for(int i = 0; i < maxn; i++)
tree[i].clear();
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
scanf("%d", &n);
int a, b, d;
for(int i = 1; i < n; i++)
{
scanf("%d%d%d", &a, &b, &d);
tree[a].push_back(node{b, d});
tree[b].push_back(node{a, d});
}
dfs(0, -1);
double ans = 1.0 * dp[0] / (n * (n - 1) / 2);
printf("%.8f\n", ans);
}
return 0;
}