Observing the Tree
All submissions for this problem are available.
Chef gives you a tree, consisting of N nodes. The nodes are numbered from 1 to N, and each node has an integer, which is equal to 0 initially. Then, Chef asks you to perform M queries.
The first type of queries is changing: here, you are given integers X, Y, A and B. Add A to the integer, associated with the node X, then add A+B to the integer, associated with the second node on the way from X to Y, then add A+2*B to the integer, associated with the third node on the way from X to Y, and so on. As you know, there is only one simple path from X to Y.
The second type of queries is a question: here, you are given integers X and Y. Output the sum of all integers, associated with nodes on the way from X to Y.
The third type of queries is a rollback: here, you are given an integer X. All the integers associated with the nodes return to the state after the X-th changing query. If X is 0, then all of them become equal to zero, as in the very beginning.
The first line of an input consists of two integers - N and M.
Then, N−1 lines follow. These N−1 lines describe the tree structure. Each line consists of two integers - X and Y, and that means that there is an edge between node X and node Y.
Then, M lines follow. A single line denotes a single query, which has one of the following forms: (See the sample for the detailed explanation)
- c X1 Y1 A B - changing query,
- q X1 Y1 - question query,
- l X1 - rollback query.
As you can see, the numbers X and Y aren't given to you directly. For the rollback query, actual number X will be equal to (X1+lastans) modulo (total number of changing queries before this query + 1). For the changing and question queries, X will be equal to ((X1+lastans) modulo N)+1 and Y will be equal to ((Y1+lastans) modulo N)+1, where lastans denotes the last number that you have output, or zero if you haven't output any numbers yet.
For each question query output the answer on a single line.
- 1 ≤ N, M ≤ 100000 (105)
- 0 ≤ A, B ≤ 1000
- 0 ≤ X1, Y1 ≤ 100000 (105)
Input: 5 7 1 2 2 3 3 4 4 5 c 1 4 2 3 c 2 3 5 10 q 1 3 l 1 q 1 3 l 1 q 1 3 Output: 35 0 15
As you can see, the tree in the sample is like a line. Let's denote the first state of integers 0 0 0 0 0, where the i-th integer means the integer associated with the node i.
In the first changing query "c 1 4 2 3", the actual numbers are X = (1 + 0) modulo 5 + 1 = 2, Y = (4 + 0) modulo 5 + 1 = 5. Hence the state will be 0 2 5 8 11 after this query.
After the second changing query "c 2 3 5 10", the state will be 0 2 10 23 11 for similar reason.
In the next question query, the actual numbers are X = (1 + 0) modulo 5 + 1 = 2, Y = (3 + 0) modulo 5 + 1 = 4. Hence the answer must be 2 + 10 + 23 = 35.
In the first rollback query "l 1", the actual number is X = (1 + 35) modulo (2 + 1) = 36 modulo 3 = 0, since lastans = 36. Thus the state will be rollbacked to 0 0 0 0 0.
Then the answer of the next question query "q 1 3" must be 0, because all integers are currently 0.
In the second rollback query "l 1", the actual number is X = (1 + 0) modulo (2 + 1) = 1, since lastans = 0. Thus the state will be 0 2 5 8 11, which is the state after the first changing query.
Then the answer of the last question query must be 2 + 5 + 8 = 15.
|Tags||feb13, hard, heavy-light, persistence, xcwgf666|
|Time Limit:||5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.