3656 - Salary Inequity 3656 - Injusticia Salarial 3656 - Salary Inequity

Statistics Sub: 304 | AC: 52 | AC%: 17,11 | Score: 2,94
Created by 2014 Northwest Pacific Regional Contest
Added by kko (2016-06-01)
Limits
Total Time: 11000 MS |Memory: 512 MB | Output: 64 MB | Size: 9 KB
Enabled languages
Available in

Description

There is a large company of N employees. With the exception of one employee, everyone has a direct supervisor. The employee with no direct supervisor is indirectly a supervisor of all other employees in the company. We say that employee X is a subordinate of employee Y if either Y is the direct supervisor of X, or the direct supervisor of X is a subordinate of Y.

One day, the HR department decides that it wants to investigate how much inequity there is in the company with respect to salaries. For a given employee, the inequity of the employee is the difference between the minimum salary of that employee and all his/her subordinates and the maximum salary of that employee and all his/her subordinates.
HR wants to be able to compute the inequity for any employee quickly. However, this is complicated by the fact that an employee will sometimes give himself/herself, along with all his/her subordinates, a raise. Can you help?
En una gran empresa formada por N empleados, todos (exceptuando a uno solo) tienen un supervisor directo. El empleado sin supervisor directo es indirectamente supervisor de todos los empleados de la empresa. Se dice que un empleado X es un subordinado del empleado Y si Y es el supervisor directo de X o si el supervisor directo de X es un subordinado de Y.

Cierto día, el departamento de recursos humanos decidió investigar cuánta injusticia existe en la empresa con relación a los salarios. Dado un empleado, la injusticia de este se mide como la diferencia del mínimo salario obtenido entre el empleado y todos sus subordinados y el máximo salario del empleado y todos sus subordinados.

El departamento de recursos humanos quiere calcular la injusticia de un empleado rápidamente. No obstante, esto es complicado porque en ocasiones un empleado puede otorgarse un aumento a sí mismo y a todos sus subordinados simultáneamente. ¿Pudiera usted ayudar?

There is a large company of N employees. With the exception of one employee, everyone has a direct supervisor. The employee with no direct supervisor is indirectly a supervisor of all other employees in the company. We say that employee X is a subordinate of employee Y if either Y is the direct supervisor of X, or the direct supervisor of X is a subordinate of Y.

One day, the HR department decides that it wants to investigate how much inequity there is in the company with respect to salaries. For a given employee, the inequity of the employee is the difference between the minimum salary of that employee and all his/her subordinates and the maximum salary of that employee and all his/her subordinates.
HR wants to be able to compute the inequity for any employee quickly. However, this is complicated by the fact that an employee will sometimes give himself/herself, along with all his/her subordinates, a raise. Can you help?

Input specification

The first line of input contains a number T representing the number of companies you will be analyzing for inequity. T will be at most 20.

For each company, there will be a line containing an integer N (2 <= N <= 1000000), representing the number of employees at the company. Each employee is assigned an ID which is a unique integer from 1 to N. The next line will contain N - 1 integers. The Kth integer in that line is the ID of the direct supervisor of employee (K + 1). The next line will contain N integers, the Kth integer in this line being the salary of employee K. The next line contains an integer Q (1 <= Q <= 10000), the number of events that you will need to process. There are two types of events to process - raises and inequity queries. In the event of a raise, the line will start with the letter R followed by the ID of the employee and an integer representing the increase in salary for that employee and all his/her subordinates. In the event of an inequity query, the line will start with the letter Q followed by the ID of the employee for whom inequity needs to be determined.

For every employee K, the ID of his/her supervisor will be less than K. Initial salaries will range from 1 to 1000. No raise will exceed 1000.
La primera línea de la entrada contiene un número T que representa el número de empresas a las que usted le analizará su injusticia. T será a lo sumo 20. 

Por cada empresa, se tendrá una línea con un entero N (2 <= N <= 1000000) que representa el número de empleados de esta. A cada empleado se le asigna un ID que es un entero único entre 1 y N. La siguiente línea estará formada por N - 1 enteros. El K-ésimo de dicha línea es el ID del supervisor directo del empleado (K + 1). La siguiente línea almacenará N enteros, el K-ésimo entero en esta línea representará al salario del empleado K. La siguiente línea contiene un entero Q (1 <= Q <= 10000), el número de eventos que usted necesitará procesar. Existen dos tipos de eventos – aumentos salariales y consultas de injusticia. En el evento de aumento salarial, la línea comenzará con la letra R, seguida por el identificador del empleado y un entero indicando el incremento de salario que deberá aplicarse al empleado y a todos sus subordinados. En el evento de consulta de injusticia, la línea comenzará por la letra Q, seguida del ID del empleado para el cuál se necesita determinar el valor de injusticia.

Para cada empleado K, el ID de su supervisor será menor que K. Los salarios iniciales se encontrarán en el rango de 1 a 1000. Ningún aumento salarial excederá el valor de 1000.
The first line of input contains a number T representing the number of companies you will be analyzing for inequity. T will be at most 20.

For each company, there will be a line containing an integer N (2 <= N <= 1000000), representing the number of employees at the company. Each employee is assigned an ID which is a unique integer from 1 to N. The next line will contain N - 1 integers. The Kth integer in that line is the ID of the direct supervisor of employee (K + 1). The next line will contain N integers, the Kth integer in this line being the salary of employee K. The next line contains an integer Q (1 <= Q <= 10000), the number of events that you will need to process. There are two types of events to process - raises and inequity queries. In the event of a raise, the line will start with the letter R followed by the ID of the employee and an integer representing the increase in salary for that employee and all his/her subordinates. In the event of an inequity query, the line will start with the letter Q followed by the ID of the employee for whom inequity needs to be determined.

For every employee K, the ID of his/her supervisor will be less than K. Initial salaries will range from 1 to 1000. No raise will exceed 1000.

Output specification

For each inequity query, print the inequity of the employee on its own line.
Por cada consulta de injusticia, imprima la injusticia del empleado en su propia línea.
The first line of input contains a number T representing the number of companies you will be analyzing for inequity. T will be at most 20.

For each company, there will be a line containing an integer N (2 <= N <= 1000000), representing the number of employees at the company. Each employee is assigned an ID which is a unique integer from 1 to N. The next line will contain N - 1 integers. The Kth integer in that line is the ID of the direct supervisor of employee (K + 1). The next line will contain N integers, the Kth integer in this line being the salary of employee K. The next line contains an integer Q (1 <= Q <= 10000), the number of events that you will need to process. There are two types of events to process - raises and inequity queries. In the event of a raise, the line will start with the letter R followed by the ID of the employee and an integer representing the increase in salary for that employee and all his/her subordinates. In the event of an inequity query, the line will start with the letter Q followed by the ID of the employee for whom inequity needs to be determined.

For every employee K, the ID of his/her supervisor will be less than K. Initial salaries will range from 1 to 1000. No raise will exceed 1000.

Sample input

1
5
1 1 2 2
10 6 8 4 5
7
Q 2
Q 3
R 4 2
Q 2
Q 1
R 2 4
Q 1

Sample output

2
0
1
5
2

Hint(s)

http://coj.uci.cu/24h/
http://coj.uci.cu/24h/
http://coj.uci.cu/24h/

Recommendation

We have carefully selected several similar problems: 3379 | 3166 | 3954 | 2378 | 2756 | 3419