记录编号	49136	评测结果	AAAAA
题目名称	小树	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-11-07 13:09:02	内存使用	0.33 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1000 + 10, INF = 0x7ffffff;
int t, n, e[N], c[N];
vector<int> G[N];
double f[N];
void DFS(int u, int d, double s) {
    for(int i=0; i<G[u].size(); i++)
        DFS(G[u][i], d+1, s + c[G[u][i]]);
    for(int i=0; i<G[u].size(); i++)
        f[u] = max(f[u], f[G[u][i]]);
    f[u] = max(f[u], s / d);
}
int main() {
    freopen("treec.in", "r", stdin);
    freopen("treec.out", "w", stdout);
    scanf("%d", &t);
    int u, v, y;
    while(t--) {
        scanf("%d", &n);
        fill_n(f+1, n, -INF);
        for(int i=0; i<=n; i++) G[i].clear();
        for(int i=1; i<n; i++) {
            scanf("%d %d %d", &u, &v, &y);
            G[u].push_back(v);
            e[v] = u, c[v] = y;
        } f[0] = 0;
        for(int i=0; i<G[0].size(); i++) {
            DFS(G[0][i], 1, c[G[0][i]]);
            f[0] = max(f[0], f[G[0][i]]);
        } printf("%lf\n", f[0]);
    }
    return 0;
}