DRTREE - Dynamically-Rooted Tree

no tags 

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.


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.


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


2 1 1 1 2
1 1 2 2
S 2
R 2
S 1


hide comments
enigmus: 2019-08-21 09:28:50

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
aimbot: 2018-01-12 18:58:57

nice problem i like it a lot

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