August 8 – 15, Plovdiv, Bulgaria

Contest Day 2 - Regions

English 1.2

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 r1 and r2, how many pairs
of employees e1 and e2 exist in the agency, such that employee e1 comes from region r1,
employee e2 comes from region r2, and e1 is a manager of e2. Every query has two parameters:
the regions r1 and r2; and its result is a single integer: the number of different pairs e1 and e2 that
satisfy the above-mentioned conditions.

TASK
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.

EXAMPLE

Sample Input

Sample Output
6 3 4
1
1 2
1 3
2 3
2 3
5 1
1 2

1 3

2 3

3 1

1 [flush standard output]

3 [flush standard output]

2 [flush standard output]

1 [flush standard output]

TESTING
If you would like to test your solution through the contest system’s test interface, the input file
you provide should include both the input data and all queries, as illustrated in the sample input
above.

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 ≤ Hk ≤ R

The home region of employee k (for 1 ≤ k ≤ N)
1 ≤ Sk < k

The supervisor of employee k (for 2 ≤ k ≤ N)
1 ≤ r1, r2 ≤ R
The regions inquired about in a given query

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 kth 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 H1 of the Chair. Each of the other N-1
lines contains two integers separated by a single space: employee k’s supervisor Sk, and
employee k’s home region Hk.

August 8 – 15, Plovdiv, Bulgaria

Contest Day 2 - Regions

English 1.2

INTERACTION
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 r1 and r2.

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

NOTE: 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.

IMPORTANT NOTE: 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.

GRADING
For a number of tests, worth a total of 30 points, R will not exceed 500.
For a number of tests, worth a total of 55 points, no region will have more than 500 employees.
The tests where both of the above conditions hold are worth 15 points.
The tests where at least one of the two conditions holds are worth 70 points.

생성자가 기록되지 않았습니다.

출처 IOI 2009