All submissions for this problem are available.
There are multiple parallel universe and one can traverse from one to another using the method of inception. A universe is reachable from another only if they are connected by an "inception line", and for two universe not connected by a direct "inception line", one might have to traverse multiple intermediate universe before reaching the destination universe. You are assured there will be exactly one path from any universe to any other.
However there's another catch for the people planning to traverse between different universe. Every universe has a time factor associated with it. Given two universe A and B with a direct "inception line" between them, assume A has a time factor S and B has a time factor T, then a job J in A will be slowed by a S T factor in B. Similarly if from B, one moves to another universe C, directly connected to it, having time factor V, then the job will be slowed down by a factor of S ( T V ) in C, and so on. Note that it may appear contradictory to common sense, but thats how things in parallel universe are.
You will be given the data of all universe with the connectivity information between them. Your task is, given two universe P and Q, to report the factor by which the job will be slowed down, when one traverses from P to Q. Since this factor can be very large, you will have to report it modulus some value, which will be given in the input. Also the time factor may have to updated and such an operation will also have to be supported. However, there will be atmost 5 update operations.
First line contains two space separated integers, N and K.
The next N-1 lines contain the connectivity information. Each line contains two space separated integers P and R, representing there is an "inception line" between P and R.
Next line contains N space separated integers, where the i-th integer is the value of the time factor for the i-th universe.
Following K lines contains the operations to be performed, each line representing an operation.
For a query operation, the first character is Q, followed by three space separated integers A, B and C.
For an update operation, the first character is U, followed by two space separated integer D and E, such the the time factor of universe D is to be changed to E.
For each of the query operations, output the factor (mod C) by which a job will be slowed down on traversing from universe A to universe B.
- 1≤N ≤ 1e5
- 1≤K ≤ 1e5
- 1≤C ≤ 1e5
- 1≤ value of a universe ≤ 1e9
2 3 2 2 3
Q 3 4 10000
Q 2 5 10000
U 2 2
Q 3 4 10000
Q 2 5 10000
First query operation represents (232) mod 10000 = 512
Second query operation represents (323) mod 10000 = 6561
After the update operation, time factor of universe 2 is changed to 2.
Third query operation represents (222) mod 10000 = 16
Fourth query operation represents (223) mod 10000 = 256
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions