CF500D New Year Santa Network

一个 $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}$ 以内

Consider the first sample. There are 6 triples: $ (1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1) $ . Because $ n=3 $ , the cost needed to build the network is always $ d(1,2)+d(2,3)+d(3,1) $ for all the triples. So, the expected cost equals to $ d(1,2)+d(2,3)+d(3,1) $ .