HDU2376 Average distance

题目链接：传送门

求树上任意两点间的路径和
的平均值

非常套路
统计每条边被经过多少次
就是两边的点数的乘积
注意精度就好

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long ll;
const int A = 200005;
struct node {
    int to, next; ll w;
} e[A];
int head[A], num;
int n, a, b, T, siz[A]; ll c, f[A];
void add(int fr, int to, ll w) {
    e[++num].next = head[fr];
    e[num].to = to;
    e[num].w = w;
    head[fr] = num;
}
void dfs(int fr, int fa) {
    siz[fr] = 1;
    for (int i = head[fr]; i; i = e[i].next) {
        int ca = e[i].to;
        if (fa == ca) continue;
        dfs(ca, fr);
        siz[fr] += siz[ca];
        f[fr] = (f[fr] + f[ca] + (double)(n - siz[ca]) * siz[ca] * e[i].w);
    }
}
int main(int argc, char const *argv[]) {
    scanf("%d", &T);
    while (T--) {
        memset(f, 0, sizeof f);
        memset(siz, 0, sizeof siz);
        memset(head, 0, sizeof head); num = 0;
        scanf("%d", &n);
        for (int i = 1; i < n; i++) {
            scanf("%d%d%lld", &a, &b, &c);
            add(a, b, c);
            add(b, a, c);
        }
        dfs(1, -1);
        printf("%.6f\n", (double)f[1] * 2.0 / double(n * (n - 1)));
    }
    return 0;
}