树世界新年即将来临!在这个世界上,顾名思义,有 n 个城市由 n - 1 条道路连接,并且对于任何两个不同的城市,它们之间总是存在一条路径。城市用 1 到 n 的整数编号,道路用 1 到 n - 1 的整数编号。我们将 d(u, v) 定义为城市 u 和城市 v 之间的路径上的道路总长度。
作为一项年度活动,树世界的人们每年只修复一条道路。结果,一条道路的长度减少了。已知在第 i 年,第 ri 条路的长度将变为 wi,比之前的长度要短。假设当前年份是第 1 年。
三位圣诞老人计划每年向树世界的所有孩子们赠送礼物。为此,他们需要做一些准备,因此他们将选择三个不同的城市 c1、c2、c3,并在每个城市创建一个仓库。第 k (1 ≤ k ≤ 3) 位圣诞老人将负责管理 ck 市的仓库。
三个圣诞老人一个人守着一个仓库,实在是太无聊了。因此,他们决定建立一个仅供圣诞老人使用的网络!构建该网络所需的成本等于 d(c1, c2) + d(c2, c3) + d(c3, c1) 美元。圣诞老人太忙了,没时间找到最好的地方,所以他们决定从 1 到 n 的所有不同数字的三元组中随机均匀地选择 c1、c2、c3。圣诞老人想知道建设网络所需成本的预期值。
然而,正如前面提到的,每年,只有一条道路的长度会减少。因此,圣诞老人想要计算每次长度变化后的预期。帮助他们计算价值。
输入
第一行包含一个整数 n (3 ≤ n ≤ 105) — 树世界中的城市数量。
接下来的 n - 1 行描述道路。其中第 i 行 (1 ≤ i ≤ n - 1) 包含三个空格分隔的整数 ai, bi, li (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ li ≤ 103),表示第 i 条路连接城市 ai 和 bi,第 i 条路的长度为 li。
下一行包含一个整数 q (1 ≤ q ≤ 105) — 道路长度变化的次数。
接下来 q 行描述长度变化。其中第 j 行 (1 ≤ j ≤ q) 包含两个空格分隔的整数 rj, wj (1 ≤ rj ≤ n - 1, 1 ≤ wj ≤ 103)。意味着在第j次修复中,第rj条路的长度变成了wj。保证wj小于当前第rj条路的长度。同一条路可以修好几次。
输出
输出q个数。对于每个给定的更改,打印一行,其中包含在 Tree World 中构建网络所需的预期成本。如果答案的绝对误差和相对误差不超过 10 - 6,则认为答案是正确的。
示例
输入 #1
3 2 3 5 1 3 3 5 1 4 2 2 1 2 2 1 1 1
输出 #1
14.0000000000 12.0000000000 8.0000000000 6.0000000000 4.0000000000
输入 #2
6 1 5 3 5 3 2 6 1 7 1 4 4 5 2 3 5 1 2 2 1 3 5 4 1 5 2
输出 #2
19.6000000000 18.6000000000 16.6000000000 13.6000000000 12.6000000000
注意
考虑第一个样本。有 6 个三元组:(1, 2, 3)、(1, 3, 2)、(2, 1, 3)、(2, 3, 1)、(3, 1, 2)、(3, 2, 1)。因为 n = 3,所以对于所有三元组,构建网络所需的成本始终为 d(1, 2) + d(2, 3) + d(3, 1)。因此,预期成本等于 d(1, 2) + d(2, 3) + d(3, 1)。