Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

There is a tree consist of $N$ nodes and $N-1$ edges. The $i^{th}$ node contains $S_i$ liters of water with a temperature of $T_i$ degrees. The temperature of water in each node remains unchanged until they are mixed with more water.

You have to perform $Q$ queries of two types on the tree:

$Type$$1:$ You will be given a path from node $U$ to node $V$. What will be the temperature of the water if we mix all the water of all nodes in the path from node $U$ to node $V$. Also, you have to find the total number of liters of water in that path. Properties of the tree will remain unchanged during this type of query. When we mix water from two different nodes $a$ and $b$. The following rule will be applied:

$T_a × S_a + T_b × S_b = T_c × (S_a+S_b)$,

where $T_a$ and $T_b$ are the temperatures of water in node $a$ and node $b$ respectively. $S_a$ and $S_b$ are the numbers of the liter of water in node $a$ and node $b$. $T_c$ is the new temperature of the water after mixing.

$Type$$2:$ Update the volume and temperature of water in node $U$.

The First line contains two numbers $N$ and $Q$ $(3 \leq N, Q \leq 10^5)$. Here, $N$ is the number of nodes and $Q$ is the number of queries respectively.

Each of the next $N-1$ lines consists of two integers $U$ and $V$$(1 \leq U, V \leq N, U\neq V)$ denoting there is an edge between nodes numbered $U$ and $V$.

$N$ line follows. For each $i$ from $1$ to $N$, $i^{th}$ line will have two integers $T_i$ and $S_i$ $(1\leq T_i, S_i \leq 10^3)$. $T_i$ is the temperature of the water in the $i^{th}$ node and $S_i$ is the volume of water in liters of $i^{th}$ node.

Following $Q$ lines describe a query at each line.

$Type$ $1:$ 1 $U$ $V$ $(1 \leq U, V \leq N)$.

$Type$ $2:$ 2 $i$ $T_i$ $S_i$ $(1 \leq T_i, S_i \leq 10^3)$ where $T_i$ and $S_i$ is integer numbers denoting new temparature and water volume respectively.

For type 2 queries, change the temperature of water of $i^{th}$ node to $T_i$ and volume of water to $S_i$ liters.

For 40 Points: Every constraint is less than or equal to $10^3$.

For 100 Points: Original constraints.

For each of the Type 1 queries, print two real numbers ${X }$ and $Y$. $X$ is the average temperature and $Y$ is the total volume of water if we mix the waters of all nodes of the path from node $U$ to node $V$.

The answer will be considered correct if its relative or absolute error doesn't exceed $10^{-4}$.

Input | Output |
---|---|

5 4 1 2 2 3 2 4 1 5 30 2 80 1 70 2 50 3 100 1 1 2 5 1 5 3 2 2 70 2 1 5 3 | 60.00000 4.00000 63.33333 6.00000 62.85714 7.00000 |

Login to submit

Let the equation for mix water from two nodes aaa and bbb is Tc=(Ta×Sa+Tb×Sb)/(Sa+Sb)T_c = (T_...

Toph uses cookies. By continuing you agree to our Cookie Policy.