Easy Airthmetic Geometric Progression
All submissions for this problem are available.
In planet Krypton, the people use concalls to communicate with each other. The concall network is composed of concall devices connected to each other. The network is such that from each concall device, there is a unique path through the network to reach every other concall device.
An Edit: Note that, the connection between any two concall devices, if connected, is two way.
The network has a parameter R, constant for it throughout its use. Every concall device has some value associated with it, which is initially zero.
General Zod, a militant leader, knows that the concall network is the lifeline of the society in the planet and so wishes to slowly poison it. To do this, he introduces nanomites in the network, through a state-of-the-art program.
Whenever he runs the program on devices A and B, then all devices in the shortest path from A to B have their value incremented by a certain amount by the nanomites. The amount incremented of nodes in the path is in arithmetic geometric series, i.e., if the shortest path is A, V1, V2,.....,B, then value of A is incremented by XR1, value of V1 is incremented by 2XR2, value of V2 is incremented by 3XR3 and so on. The value of X can be different for every program run by Zod while the value of R is fixed for the network, as specified earlier.
After having run the program to change the values in the specified way of multiple devices in the network, General Zod wishes to make some queries of the values of the network to assess the correctness of his program. He wants to know that, given two devices C and D, what is now the sum of values of devices in the shortest path from C to D. Since this value may be very large, you have to report it modulo 100711433.
First line contains two integers (N and R respectively) separated by space.
In the next N-1 lines, each line contains two integers A and B, such that there is a direct connection between A and B.
Next line contains two space separated Integers (U and Q respectively) representing the total number of Update and Query operations to follow.
Next U lines follow each line asking to increment the value of certain nodes in the above specified way. Each line contains 3 space specified integers, X, A and B, where X is the parameter for the program and A and B are the devices, such that values of all devices between A and B are to be updated.
Next Q lines, each line containing two integers C and D.
Output the answer to each query as explained.
- 1 ≤ R ≤ 109
- 1 ≤ N ≤ 105
- 1 ≤ U ≤ 105
- 1 ≤ Q ≤ 105
- 1 ≤ X ≤ 109
3 3 4
3 2 5
Value of R is 2.
After first update the values of device 3 becomes 6, device 2 becomes 24, device 4 becomes 72.
After second update values of device 2 becomes 24+6=30, device 1 becomes 24, device 5 becomes 72.
For first query operation, Value + Value + Value = 108
For second query operation, Value + Value + Value = 126
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions