DRTREE - Dynamically-Rooted Tree

You are given a rooted tree with N nodes, numbered from 1 to N. Initially node 1 is the root. Each node i has a weight W[i]. You have to perform two types of operations:
"S a" - Find the sum of weights of node a's sub-tree nodes (including node a).
"R a" - Change root of the tree to a.

Input

Line 1: N (1 <= N <= 105), number of nodes.
Line 2: N space-separated integers, weights of nodes from 1 to N. i'th integer is W[i] (1 <= W[i] <= 109).
Line 3: N-1 space-separated integers, i'th integer is the parent of node i+1.
Line 4: Q, the number of operations (1 <= Q <= 105).
Lines 5 .. 5+Q-1: Every line contains a space separated character and an integer. Character describes the type of the operation, and integer is the node number.

Output

For each operation of type 'S', output the operations result in a separate line.

Example

Input:
5
2 1 1 1 2
1 1 2 2
3
S 2
R 2
S 1

Output:
4
3

Added by:Hasan Jaddouh
Date:2013-05-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2024-05-23 14:31:44
Try this testcase:
6
2 1 1 1 2 4
1 1 2 2 3
3
S 2
R 2
S 1
2021-10-13 06:59:27
A O((n+q)logn) solution using lca.
And a useful input:
5
1 2 4 8 16
1 1 2 2
8
S 1
R 5
S 1
R 3
S 4
S 2
R 4
S 2
Edit: Output:
31
5
8
26
23

Last edit: 2021-10-13 07:00:16
2021-01-14 19:12:58
getting wa..??
2019-08-21 09:28:50 enigmus
I don't understand what is written on Line 3. I'll try to interpret it so that i'th integer is an index of the node that is parent of the node with index i+1

Last edit: 2019-08-21 09:31:11
2018-01-12 18:58:57
nice problem i like it a lot
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.