Description

Cirno is a fairy who can control how cold the air is. One day she found a watermelon field. There are $n$ watermelons, connected by $n-1$ vines, forming a rooted tree. Cirno wants to freeze them and eat them slowly.

These watermelon vines have a magical property: they can amplify or attenuate the coldness of the passing cold air. Each vine has a multiplier $w_i$, meaning that after the cold air passes through it, a coldness value $x$ becomes $x\times w_i$. Each watermelon also has a coldness value, and on a hot summer day all watermelons start with coldness $0$.

Cirno performs two types of actions:

①. Release cold air of coldness $x$ at watermelon $i$. This cold air spreads along the vines toward the leaves of the "watermelon tree", and its coldness changes according to the above rule. When a watermelon has multiple outgoing vines toward leaf nodes, each vine gets cold air with the same coldness as before the split. Every watermelon along the path adds the current coldness of the air to its own coldness.

The cold air only spreads within the subtree of the release point and never toward the root.

⑨. Ask for the coldness value of watermelon $i$.

Wait, why is there a ⑨? Because silly Cirno herself sometimes forgets how much ice she has released.

So please help her compute it.

Input Format

The first line contains an integer $n$, the number of watermelons.

The watermelons are numbered $1$ to $n$, and $1$ is the root of this "watermelon tree".

The next $n-1$ lines each contain two integers $u$, $v$ and a real number $w$, indicating that there is a vine between watermelons $u$ and $v$, and its amplification/attenuation multiplier is $w$.

The next line contains an integer $m$, the number of operations.

Each of the next $m$ lines contains either two integers, or two integers and a real number.

The first number can only be $1$ or $9$.

If it is $1$, then an integer $i$ and a real number $x$ follow, meaning to release cold air of coldness $x$ at watermelon $i$.

If it is $9$, then an integer $i$ follows, meaning to query the coldness value of watermelon $i$.

Output Format

For each operation ⑨, output one line with a real number, the coldness value of the corresponding watermelon.

4
1 2 1.00000000
2 3 0.00000000
3 4 1.00000101
9
1 1 3.00000000
9 2
9 3
1 2 1.42856031
9 4
9 2
1 3 4.23333333
9 2
9 4

3.00000000
0.00000000
0.00000000
4.42856031
4.42856031
4.23333761

Hint

A subtask may have the following special property:

The "watermelon tree" degenerates into a chain.

All real numbers in the input keep 8 decimal places. A solution is accepted if and only if the absolute error from the standard answer is at most $10^{-7}$. Please pay special attention to floating-point precision.

In the actual testdata, the range of the coldness $x$ of the cold air is $[-0.1, 0.1]$.

(In the samples, the range of the coldness is $[1, 5]$.)

Problem setter: orangebird, thanks to oscar.

Translated by ChatGPT 5