hdu2376 Average distance

题面：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，即为最后所求。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
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;
}