|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||256 MB||21||8||7||35.000%|
The tree of Almost Clean Money (or ACM Tree, for short) consists of N (1≤N≤500000) vertices in which, well, (almost clean) money is growing (contrary to the old saying that money doesn’t grow on trees). The vertices are numbered from 0 to N-1, with vertex 0 being the root of the tree. Every vertex i except vertex 0 has a parent p(i) in the tree, such that p(i)<i. Initially, every vertex contains v(i) (0≤v(i)<1000000007) monetary units. Due to its special properties, the tree has attracted the attention of a large money laundering organization, who wants to use the tree for its money “cleansing” business. This organization wants to execute Q (1≤Q≤50000) operations on the tree. Each operation consists of two steps:
The organization hired you to find the answer for step 2 of each of the Q operations and promised you a hefty amount of money if you succeed.
The first line of input contains the number of tree vertices N. The next N-1 lines contain two space-separated integers, p(i) and i, each describing an edge of the tree. The next line contains N space-separated values: the initial amount of monetary units in each vertex, v(0), …, v(N-1). The next line contains the number of operations Q. Each of the next Q lines describes an operation. Each operation is described by 9 space-separated integers, in this order: K, x(1), y(1), A, B, C, D, u, v (0≤A,B,C,D<1000000007). The values x(2≤i≤K) and y(2≤i≤K) are generated as follows:
For each of the Q operations print a line containing the answer to step 2 of the operation. When computing the answer for an operation, the effects of steps 1 from previous operations need to be considered, too (i.e. after adding y(i) monetary units to a vertex x(i), these units remain added to the vertex when executing subsequent operations, too).
4 0 1 0 3 1 2 1 2 3 4 3 1000 1 1 1 0 1 0 0 2 2 0 5 1 1 2 2 2 3 1 3 7 999 999 999 999 1 3
1006 1027 1031