CF500D.New Year Santa Network

New Year is coming in Tree World! In this world, as the name implies, there are n cities connected by n - 1 roads, and for any two distinct cities there always exists a path between them. The cities are numbered by integers from 1 to n, and the roads are numbered by integers from 1 to n - 1. Let's define d(u, v) as total length of roads on the path between city u and city v.

As an annual event, people in Tree World repairs exactly one road per year. As a result, the length of one road decreases. It is already known that in the i-th year, the length of the r__i-th road is going to become w__i, which is shorter than its length before. Assume that the current year is year 1.

Three Santas are planning to give presents annually to all the children in Tree World. In order to do that, they need some preparation, so they are going to choose three distinct cities _c_1, _c_2, _c_3 and make exactly one warehouse in each city. The k-th (1 ≤ k ≤ 3) Santa will take charge of the warehouse in city c__k.

It is really boring for the three Santas to keep a warehouse alone. So, they decided to build an only-for-Santa network! The cost needed to build this network equals to d(_c_1, _c_2) + d(_c_2, _c_3) + d(_c_3, _c_1) dollars. Santas are too busy to find the best place, so they decided to choose _c_1, _c_2, _c_3 randomly uniformly over all triples of distinct numbers from 1 to n. Santas would like to know the expected value of the cost needed to build the network.

However, as mentioned, each year, the length of exactly one road decreases. So, the Santas want to calculate the expected after each length change. Help them to calculate the value.

新年即将来到树形世界！在这个世界中，顾名思义，共有 $n$ 座城市，由 $n-1$ 条道路连接；且对任意两座不同的城市，其间总存在一条路径。城市编号为 $1$ 至 $n$ 的整数，道路编号为 $1$ 至 $n-1$ 的整数。我们定义 $d(u,\,v)$ 为城市 $u$ 与城市 $v$ 之间路径上所有道路长度的总和。

作为一年一度的活动，树形世界的人们每年恰好修复一条道路。因此，某条道路的长度会减小。已知在第 $i$ 年，第 $r_i$ 条道路的长度将变为 $w_i$，该值严格小于其此前的长度。假设当前年份为第 $1$ 年。

三位圣诞老人计划每年向树形世界的所有儿童赠送礼物。为此，他们需要进行一些准备工作，故将选择三座互不相同的城市 $c_1,\,c_2,\,c_3$，并在每座城市中各建立一座仓库。第 $k$ 位（$1\le k\le 3$）圣诞老人将负责城市 $c_k$ 中的仓库。

三位圣诞老人独自看管一座仓库实在太过乏味。因此，他们决定共建一个“仅限圣诞老人使用”的网络！构建该网络所需的成本为 $d(c_1,\,c_2) + d(c_2,\,c_3) + d(c_3,\,c_1)$ 美元。圣诞老人太忙，无暇寻找最优选址方案，因此决定在 $1$ 至 $n$ 中所有互不相同的三元组 $(c_1,\,c_2,\,c_3)$ 上均匀随机地选取。圣诞老人希望知道构建该网络所需成本的期望值。

然而，如前所述，每年恰好有一条道路的长度会减小。因此，圣诞老人希望在每次长度变更后重新计算该期望值。请帮助他们完成这一计算。

The first line contains an integer n (3 ≤ n ≤ 105) — the number of cities in Tree World.

Next n - 1 lines describe the roads. The i-th line of them (1 ≤ i ≤ n - 1) contains three space-separated integers a__i, b__i, l__i (1 ≤ a__i, b__i ≤ n, a__i ≠ b__i, 1 ≤ l__i ≤ 103), denoting that the i-th road connects cities a__i and b__i, and the length of i-th road is l__i.

The next line contains an integer q (1 ≤ q ≤ 105) — the number of road length changes.

Next q lines describe the length changes. The j-th line of them (1 ≤ j ≤ q) contains two space-separated integers r__j, w__j (1 ≤ r__j ≤ n - 1, 1 ≤ w__j ≤ 103). It means that in the j-th repair, the length of the r__j-th road becomes w__j. It is guaranteed that w__j is smaller than the current length of the r__j-th road. The same road can be repaired several times.

第一行包含一个整数 $n$（$3 \leq n \leq 10^5$）—— 表示 Tree World 中的城市数量。

接下来的 $n-1$ 行描述道路。其中第 $i$ 行（$1 \leq i \leq n-1$）包含三个用空格分隔的整数 $a_i$、$b_i$、$l_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq l_i \leq 10^3$），表示第 $i$ 条道路连接城市 $a_i$ 和 $b_i$，且该道路的长度为 $l_i$。

下一行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 表示道路长度修改操作的次数。

接下来的 $q$ 行描述长度修改操作。其中第 $j$ 行（$1 \leq j \leq q$）包含两个用空格分隔的整数 $r_j$、$w_j$（$1 \leq r_j \leq n-1$，$1 \leq w_j \leq 10^3$）。它表示在第 $j$ 次维修中，第 $r_j$ 条道路的长度变为 $w_j$。保证 $w_j$ 小于第 $r_j$ 条道路当前的长度。同一条道路可能被多次维修。

Output q numbers. For each given change, print a line containing the expected cost needed to build the network in Tree World. The answer will be considered correct if its absolute and relative error doesn't exceed 10 - 6.

输出 q 个数字。对于每次给定的修改，打印一行，包含在“树世界”（Tree World）中构建该网络所需的期望花费。若答案的绝对误差和相对误差均不超过 $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).

考虑第一个样例。共有 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)$。