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.
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.
Input: 5 2 1 1 1 2 1 1 2 2 3 S 2 R 2 S 1 Output: 4 3