LCC '18 Contest 2 S5 - Salaries

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

The WLM corporation has asked for your help in creating a system to determine employee salaries. WLM has N employees with ids from 1 to N such that employee 1 is the CEO. Each employee except for the CEO has exactly one boss. We say that employee A is a superior of employee B if A is the boss of B or A is a superior of the boss of B. The team of employee A is defined as the set of employees that have A as their superior and A themselves. WLM would like to be able to process the following two queries efficiently:

  • c A S: change the salary of employee A to S.
  • q A: compute the total salary of employee A's team.

Input Specification

The first line of input contains one integer N\ (2 \le N \le 100\ 000), the number of employees in the company. The next N lines each two integers B_i, S_i (1 \le B_i \le i, 1 \le S_i < 10\ 000), the boss and salary of employee I, respectively. B_1 will be equal to zero as employee 1 is the CEO. The next line contains a single integer Q\ (1 \le Q \le 200\ 000), the number of queries to process. The next Q lines each contain a single query in the format described above.

Output Specification

For each query of type q A, print the answer on a separate line.

Sample Input 1

5
0 1
1 1
1 1
2 1
2 1
5
q 1
c 4 2
q 2
c 3 5
q 1

Sample Output 1

5
4
10

Comments

There are no comments at the moment.