Game on S♂play
TimeLimit:8000MS MemoryLimit:131072KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
Uncle Fang is learning Splay. When he heard about the rotate operation, he would like to play a game with Captain Chen. There is a tree with n nodes initially, and the node 1 is the root. The i-th nodes gets a weight of wi, and an attribute of interesting value defined as the sum of the weight of it’s descendants. Following are two operations in this tree:
1.do a rotation on a node x. The rotation is the common rotation in splay tree, it can be right-rotation or left-rotation, as demonstrated in the following picture. If it's impossible to rotate, just ignore it!
2.ask Captain Chen the product of interesting values of the nodes in a subtree rooted at node x.
1.do a rotation on a node x. The rotation is the common rotation in splay tree, it can be right-rotation or left-rotation, as demonstrated in the following picture. If it's impossible to rotate, just ignore it!
2.ask Captain Chen the product of interesting values of the nodes in a subtree rooted at node x.
Input
There are several cases.The first line of the input contains a single integer T (T <= 30) which is the number of test cases.Then comes the T test cases .
For each case, the first line contains two integer numbers n and m(1<=n, m<=100000).
The following n lines describe the tree. In the i-th line, there was three number wi, xi, yi,(0<=w<=100000, 0<=x, y<=n) indicate the weight of node i, the left child of node i, and the right child of node i. If xi or yi equals to 0, it means node i has no such child.
And the following m lines describe the operations. There are two numbers p x in each line. If p is 0, it means do right-rotation on node x; If p is 1, it means do left-rotation on node x; if p is 2, it means ask the product of interesting values of the nodes in a subtree rooted at node x.
For each case, the first line contains two integer numbers n and m(1<=n, m<=100000).
The following n lines describe the tree. In the i-th line, there was three number wi, xi, yi,(0<=w<=100000, 0<=x, y<=n) indicate the weight of node i, the left child of node i, and the right child of node i. If xi or yi equals to 0, it means node i has no such child.
And the following m lines describe the operations. There are two numbers p x in each line. If p is 0, it means do right-rotation on node x; If p is 1, it means do left-rotation on node x; if p is 2, it means ask the product of interesting values of the nodes in a subtree rooted at node x.
Output
For the k-th test case, first output “Case #k:” in a separate line.Then for each query,output a single num in each line after mod 1000000007.
SampleInput
1 3 4 1 2 3 1 0 0 1 0 0 2 1 0 1 2 2 2 1
SampleOutput
Case #1: 3 6 2 HintAs the input data may cause the stack overflow if you use some recursion solution. Add #pragma comment (linker,"/STACK:102400000,102400000") in C++ language.