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 \lt 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.