22316번 - Regions 다국어인터랙티브

The United Nations Regional Development Agency (UNRDA) has a very well defined organizational structure. It employs a total of N people, each of them coming from one of R geographically distinct regions of the world. The employees are numbered from 1 to N inclusive in order of seniority, with employee number 1, the Chair, being the most senior. The regions are numbered from 1 to R inclusive in no particular order. Every employee except for the Chair has a single supervisor. A supervisor is always more senior than the employees he or she supervises.

We say that an employee A is a manager of employee B if and only if A is B’s supervisor or A is a manager of B’s supervisor. Thus, for example, the Chair is a manager of every other employee. Also, clearly no two employees can be each other’s managers.

Unfortunately, the United Nations Bureau of Investigations (UNBI) recently received a number of complaints that the UNRDA has an imbalanced organizational structure that favors some regions of the world more than others. In order to investigate the accusations, the UNBI would like to build a computer system that would be given the supervision structure of the UNRDA and would then be able to answer queries of the form: given two different regions r₁ and r₂, how many pairs of employees e₁ and e₂ exist in the agency, such that employee e₁ comes from region r₁, employee e₂ comes from region r₂, and e₁ is a manager of e₂. Every query has two parameters: the regions r₁ and r₂; and its result is a single integer: the number of different pairs e₁ and e₂ that satisfy the above-mentioned conditions.

Write a program that, given the home regions of all of the agency’s employees, as well as data on who is supervised by whom, interactively answers queries as described above.

Your program must read from standard input the following data:

• The first line contains the integers N, R and Q, in order, separated by single spaces.
• The next N lines describe the N employees of the agency in order of seniority. The k th of these N lines describes employee number k. The first of these lines (i.e., the one describing the Chair) contains a single integer: the home region H₁ of the Chair. Each of the other N-1 lines contains two integers separated by a single space: employee k’s supervisor S_k, and employee k’s home region H_k.

• 1 ≤ N ≤ 200,000 The number of employees
• 1 ≤ R ≤ 25,000 The number of regions
• 1 ≤ Q ≤ 200,000 The number of queries your program will have to answer
• 1 ≤ H_k ≤ R The home region of employee k (for 1 ≤ k ≤ N)
• 1 ≤ S_k < k The supervisor of employee k (for 2 ≤ k ≤ N)
• 1 ≤ r₁, r₂ ≤ R The regions inquired about in a given query

After reading the input data, your program must start alternately reading queries from standard input and writing query results to standard output. The Q queries must be answered one at a time; your program must send the response to the query it has already received before it can receive the next query.

Each query is presented on a single line of standard input and consists of two different integers separated by a single space: the two regions r₁ and r₂.

The response to each query must be a single line on standard output containing a single integer: the number of pairs of UNRDA employees e₁ and e₂, such that e₁‘s home region is r₁, e₂’s home region is r₂ and e₁ is a manager of e₂.

The test data will be such that the correct answer to any query given on standard input will always be less than 1,000,000,000.

In order to interact properly with the grader, your program needs to flush standard output after every query response. It also needs to avoid accidentally blocking when reading standard input, as might happen for instance when using scanf("%d\n"). Please see the technical info sheet for instructions on how to do this properly.