Problem Brief

Key Sum Management

INTERNOA

A quick note: I changed the input 'operations' to a 2D String array to accommodate the 'Re' and 'Ro' entries. Other than this modification, the question should match the original prompt about 98% 🦉

You are given an initial key tree. A level is the number of parent keys corresponding to a given key of the key tree. Initial values of keys are 0.

Example:

Key 1 with value X1 would be at level 0.

Key 2, Key 3 at level 1, and so on.

There is a sequence of Rotation and Rekey operations that can happen:

Rotation: Ro p v means that a new key (v) needs to be added to parent p. Initial value is 0, though referred to as X_v in the figure.

Rekey: Re I z means that for a level (I) and the number (z) to update the value of all the keys on the same level and their subsequent children until the leaves. The new value would be the previous value of the key + z.

For Example:

Ro 1 9 would give us:

Ro 1 4 would give us:

Given an initial tree with n nodes and q operations sequence of Ro and Re operations, find the sum of values for all the keys.

1Example 1

Input

operations = [["1", "2"], ["2", "4"], ["1", "3"], ["4", "5"], ["Re", "1", "10"], ["Ro", "4", "6"], ["Re", "2", "4"], ["Re", "3", "4"]], n = 5, q = 4

Output

Explanation

n/a

2Example 2

Input

operations = [["2", "1"], ["3", "1"], ["4", "2"], ["5", "1"], ["Ro", "4", "6"], ["Re", "2", "91277"], ["Re", "1", "50944"], ["Ro", "1", "7"], ["Re", "1", "17666"]], n = 5, q = 5

Output

3607116

Explanation

n/a

Constraints

Limits and guarantees your solution can rely on.

1 ≤ n, q ≤ 10^5

1 ≤ z ≤ 10^5, where z is the number added in the Rekey query.

All other inputs satisfy the constraints and problem requirements.

In the Rotation query, the new key v always equals the current number of nodes in the tree + 1.