DRTREE  DynamicallyRooted 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 subtree nodes (including node a).
"R a"  Change root of the tree to a.
Input
Line 1: N (1 <= N <= 10^{5}), number of nodes.
Line 2: N spaceseparated integers, weights of nodes from 1 to N. i'th integer is W[i] (1 <= W[i] <= 10^{9}).
Line 3: N1 spaceseparated integers, i'th integer is the parent of node i+1.
Line 4: Q, the number of operations (1 <= Q <= 10^{5}).
Lines 5 .. 5+Q1: 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
hide comments
mohammadyay:
20240523 14:31:44
Try this testcase:


psz2007:
20211013 06:59:27
A O((n+q)logn) solution using lca.


darshan_07:
20210114 19:12:58
getting wa..?? 

enigmus:
20190821 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: 20190821 09:31:11 

aimbot:
20180112 18:58:57
nice problem i like it a lot 
Added by:  Hasan Jaddouh 
Date:  20130513 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own problem 