昕晨最近在写科幻体小说，他打算搞一个圣诞老人网络，且听他娓娓道来：

新的一年即将来到！在这个世界上，有n个城市和n-1条道路。对于任何两个不同的城市，它们之间总是存在一条路径。城市用1到n的整数进行编号，道路用1到n-1的整数进行编号。定义d（u，v）表示城市u和城市v之间道路的总长度。

作为一项年度活动，人们每年只维修一条道路。因此，每年总会有一条道路的长度缩短了。众所周知，在第i年，第r_i条道路的长度将缩短为w_i。假设当前年份为第1年。

三位圣诞老人计划每年给所有儿童赠送礼物。为了做到这一点，他们需要做一些准备，因此他们将选择三个不同的城市c₁、c₂、c₃，并在每个城市建立一个仓库。第k个（1 ≤ k ≤ 3）圣诞老人将负责c_k市的仓库。

三个圣诞老人单独呆在一个仓库里真的很无聊。所以，他们决定建立一个只为圣诞老人服务的网络！构建该网络所需的成本等于d（c₁，c₂）+d（c₂，c₃）+d（c₃，c₁）。圣诞老人没有时间去找最好的地方，所以他们决定从1到n的不同数字中随机选择c₁，c₂，c₃。圣诞老人们想知道构建网络所需成本的期望值。

然而，如上所述，每年都有一条道路的长度减少。因此，圣诞老人希望计算每次长度变化后的期望值。帮助他们计算一下吧。

第一行包含整数n（3≤n≤10⁵），表示城市数量。

随后的n-1行描述道路。第i行（1≤i≤n-1）包含三个空格分隔的整数a_i、b_i和l_i（1≤a_i，b_i≤n，a_i≠b_i，1≤l_i≤10³），表示第i条道路连接城市a_i和b_i，第i条路的长度为l_i。

随后一行包含整数q（1≤q≤10⁵）-道路长度变化的数量。

接下来的q行描述道路长度的变化。第j行（1≤j≤q）包含两个空格分隔的整数r_j，w_j（1≤r_j≤n-1, 1≤w_j≤10³). 这意味着在第j次维修时，道路r_j的长度变为w_j。数据确保w_j小于道路r_j的当前长度。同一条道路可以维修多次。

输出q个数字。对于每个给定的长度变化，打印一行，其中包含构建网络所需的预期成本。输出结果保留10位小数。

考虑第一个例子。有六个三元组：(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)。

LZC2022+天梯赛#28G