Practice on Toph

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

Water in a Tree

By Peregrine_Falcon · Limits 1s, 512 MB

There is a tree consist of NN nodes and N1N-1 edges. The ithi^{th} node contains SiS_i liters of water with a temperature of TiT_i degrees. The temperature of water in each node remains unchanged until they are mixed with more water.

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

TypeType1:1: You will be given a path from node UU to node VV. What will be the temperature of the water if we mix all the water of all nodes in the path from node UU to node VV. 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 aa and bb. The following rule will be applied:

Ta×Sa+Tb×Sb=Tc×(Sa+Sb)T_a × S_a + T_b × S_b = T_c × (S_a+S_b),

where TaT_a and TbT_b are the temperatures of water in node aa and node bb respectively. SaS_a and SbS_b are the numbers of the liter of water in node aa and node bb. TcT_c is the new temperature of the water after mixing.

TypeType2:2: Update the volume and temperature of water in node UU.

Input

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

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

NN line follows. For each ii from 11 to NN, ithi^{th} line will have two integers TiT_i and SiS_i (1Ti,Si103)(1\leq T_i, S_i \leq 10^3). TiT_i is the temperature of the water in the ithi^{th} node and SiS_i is the volume of water in liters of ithi^{th} node.

Following QQ lines describe a query at each line.

TypeType 1:1: 1 UU VV (1U,VN)(1 \leq U, V \leq N).
TypeType 2:2: 2 ii TiT_i SiS_i (1Ti,Si103)(1 \leq T_i, S_i \leq 10^3) where TiT_i and SiS_i is integer numbers denoting new temparature and water volume respectively.

For type 2 queries, change the temperature of water of ithi^{th} node to TiT_i and volume of water to SiS_i liters.

For 40 Points: Every constraint is less than or equal to 10310^3.
For 100 Points: Original constraints.

Output

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

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

Sample

InputOutput
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

    Discussion

    Statistics


    75% Solution Ratio

    gokul.rajEarliest, 1M ago

    merIinFastest, 0.1s

    merIinLightest, 21 MB

    merIinShortest, 2447B

    Submit

    Login to submit

    Editorial

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

    Related Contests

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