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
A O((n+q)logn) solution using lca.
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+1Last edit: 2019-08-21 09:31:11
nice problem i like it a lot