← 返回题目列表

Codeforces · 500/D

D. 新年圣诞老人网络

中文机器翻译题面 查看原题

树世界新年即将来临!在这个世界上,顾名思义,有 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)。