题目描述

一个 $n$ 个节点的树上进行 $q$ 次操作，每次操作将第 $r$ 条边的长度修改成 $w$。

用 $d(x,y)$ 表示从点 $x$ 到 $y$ 的距离。

在树上等概率选取三个点 $c_1,c_2,c_3$ ，求在每次操作后 $d(c_1,c_2)+d(c_1,c_3)+d(c_2,c_3)$ 的期望值。

输入格式

• 第一行，一个数字 $n$，表示树的节点数。
• 之后的 $n-1$ 行中，每行三个整数 $a,b,l$，表示树中有一条连接 $a$ 到 $b$ 长度为 $l$ 的边。
• 下一行，一个数字 $q$ 为长度修改次数。
• 接下来 $q$ 行，每行两个整数 $r$ 和 $w$ 表示将第 $r$ 条边的长度修改成 $w$ 。

输出格式

$q$ 行，第 $i$ 行输出在第 $i$ 次操作后，$d(c_1,c_2)+d(c_1,c_3)+d(c_2,c_3)$ 的期望值，需要保证你的输出和正确答案的误差在 $10^{-6}$ 以内