There is a tree consist of nodes and edges. The node contains liters of water with a temperature of degrees. The temperature of water in each node remains unchanged until they are mixed with more water.
You have to perform queries of two types on the tree:
You will be given a path from node to node . What will be the temperature of the water if we mix all the water of all nodes in the path from node to node . 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 and . The following rule will be applied:
where and are the temperatures of water in node and node respectively. and are the numbers of the liter of water in node and node . is the new temperature of the water after mixing.
Update the volume and temperature of water in node .
The First line contains two numbers and . Here, is the number of nodes and is the number of queries respectively.
Each of the next lines consists of two integers and denoting there is an edge between nodes numbered and .
line follows. For each from to , line will have two integers and . is the temperature of the water in the node and is the volume of water in liters of node.
Following lines describe a query at each line.
2 where and is integer numbers denoting new temparature and water volume respectively.
For type 2 queries, change the temperature of water of node to and volume of water to liters.
For 40 Points: Every constraint is less than or equal to .
For 100 Points: Original constraints.
For each of the Type 1 queries, print two real numbers and . is the average temperature and is the total volume of water if we mix the waters of all nodes of the path from node to node .
The answer will be considered correct if its relative or absolute error doesn't exceed .
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