1256. 小树

【题目描述】

这有一棵带根的树有 $N$ 个节点标号从 $0$ 到 $N-1$。根标号为 $0$。每条边连接两个节点，并且有权重。你的工作是找到一个顶点集合 $S \{s_1,s_2,\cdots,s_m\} (0\le m < N)$，满足以下条件：

 （1）根不在集合 $S$ 中；

 （2）集合元素节点除树根外没有其他公共祖先。

 （3）设 $p_i$ 是从根到 $s_i$ 的路径权重之和，$d_i$ 是从根到 $s_i$ 的边数总和，则比值 $ \sum p_i / \sum d_i $ 是最大的。

【输入格式】

输入第一行有一个整数 $T$ 表示测试数据个数。 每组数据第一行包含一个整数 $N (1≤N≤1000)$，表示树的节点个数。 接下来 $N-1$ 行每行包括 $3$ 个整数 $u, v, w$ ，表示一条有向边从 $u$ 到 $v$ 权重为 $w$。

【输出格式】

每组数据输出一个实数，表示符合题意的集合 $S$ 的最大比值。

【样例输入】

3
1
2
0 1 2
3
0 1 1
0 2 2

【样例输出】

0.00
2.00
2.00

【评测方式】

评测插件判断该答案与标准答案差距不超过 0.01 即可算做正确。每答对一个询问得到 1/T 的分数。