## LCC '18 Contest 2 S5 - Salaries

View as PDF

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